2026年3月GESP真题及题解（C++三级）：二进制回文串

2026年3月GESP真题及题解（C++三级）：二进制回文串

题目描述

对于一个正整数

n

n

n，我们将其转换为不含前导零的二进制表示，如果这个二进制序列从左向右读与从右向左读完全相同，则称该数为二进制回文数。例如，

9

9

9 的二进制表示为

(

1001

)

2

(1001)_2

(1001)2​，是二进制回文数；

12

12

12 的二进制表示为

(

1100

)

2

(1100)_2

(1100)2​，不是二进制回文数。

你的任务是：给定一个正整数

n

n

n，计算在

1

1

1 到

n

n

n 的范围内二进制回文数的数量。

输入格式

输入一行，包含一个正整数

n

n

n。

输出格式

输出一行，包含一个数，表示在

1

1

1 到

n

n

n 的范围内二进制回文数的数量。

输入输出样例 1

输入 1

15

输出 1

6

说明/提示

样例解释

样例 1 中，

1

1

1 到

15

15

15 范围内

1

1

1、

3

3

3、

5

5

5、

7

7

7、

9

9

9、

15

15

15 是二进制回文数。

数据范围

1

≤

n

≤

10

5

1 \\leq n \\leq 10^5

1≤n≤105。

思路分析（方法1）

本题要求统计从 1 到给定正整数 n 之间，所有二进制表示为回文的数的个数。 二进制回文的定义是：将一个正整数转换为不含前导零的二进制串，该串从左向右读与从右向左读完全相同。

由于 n ≤ 10⁵，直接枚举每个数并判断其二进制是否为回文是可行的。 判断方法（双指针法）：

• 对于一个整数 x，不断除以 2 取余数，得到它的二进制位（低位在前，高位在后），并记录位数 k。
• 双指针判断回文（比较第 i 位与倒数第 i 位）： i 从 1 到 k/2，比较 a[i] 与 a[k+1-i] 是否相等（注意 a 从下标 1 开始存储）。
• 若所有对应位都相等，则是二进制回文数；否则不是。

时间复杂度 O(n log n)，空间复杂度 O(log n)。

代码实现（方法1）

#include <bits/stdc++.h>
using namespace std;

int n; // 输入的上限
int a[30]; // 临时数组，存放二进制位（下标从1开始）
int cnt = 0; // 计数器，记录二进制回文数的个数

// 判断整数 x 是否为二进制回文数
bool check(int x) {
int k = 0; // k 记录二进制位数
// 将 x 转换为二进制，低位存储在 a[1], a[2], … 中
while (x) {
a[++k] = x % 2; // 取最低位
x /= 2; // 去掉最低位
}
// 双指针判断回文：比较第 i 位与倒数第 i 位
for (int i = 1; i <= k / 2; i++) {
if (a[i] != a[k + 1 – i])
return false;
}
return true;
}

int main() {
cin >> n; // 读入上限 n
for (int i = 1; i <= n; i++) {
if (check(i)) // 若 i 是二进制回文数
cnt++; // 计数器加1
}
cout << cnt << endl; // 输出结果
return 0;
}

功能分析（方法1）

• 输入处理：从标准输入读取一个正整数 n。
• 枚举判断：对 1 到 n 的每个整数 i，调用 check(i) 判断其二进制是否为回文。
• 回文判断：
  • check 函数通过连续除以 2 取余数，得到 i 的二进制位（低位在前）。
  • 使用循环比较对应位置的二进制位是否相同，若全部相同则返回 true，否则返回 false。
• 计数输出：累加满足条件的个数，最后输出结果。

思路分析（方法2）

本题要求统计 1 到 n 范围内所有二进制表示为回文的数的个数。 二进制回文的定义：将一个正整数转换为不含前导零的二进制字符串后，该字符串正读与反读相同。

由于 n ≤ 10⁵，直接枚举每个数并判断其二进制是否为回文是可行的。 判断方法（字符串法）：

• 对每个数 x，将其转换为二进制串：用 x % 2 取出最低位，转换为字符 '0' 或 '1'，依次压入字符串 s 中。这样得到的 s 是最低位在前的逆序二进制串。
• 将 s 复制一份到 tmp，然后将 s 反转，得到正常顺序的二进制串。
• 比较反转后的 s 与 tmp：若相等，说明原二进制串是回文（因为 tmp 是逆序，反转后应与正序相等）。

例如，x=9，二进制为 1001。

• 循环：9%2=1 → s=“1”，9/2=4；4%2=0 → s=“10”，4/2=2；2%2=0 → s=“100”，2/2=1；1%2=1 → s=“1001”，1/2=0 结束。
• s=“1001”（逆序），tmp=“1001”。反转 s → “1001”，tmp==s 成立，所以是回文。

代码实现（方法2）

#include <bits/stdc++.h>
using namespace std;

int n; // 输入的上限
int cnt = 0; // 计数器，记录二进制回文数的个数

// 判断整数 x 是否为二进制回文数
bool check(int x) {
string s; // 临时存储二进制串（初始为空）
while (x) { // 当 x 不为 0 时循环
char c = (x % 2) + '0'; // 取出最低位，转换为字符 '0' 或 '1'
s.push_back(c); // 将字符添加到 s 末尾
x /= 2; // 去掉最低位
}
// 此时 s 中存储的是原二进制串的逆序（低位在前）
string tmp = s; // 备份逆序串
reverse(s.begin(), s.end()); // 将 s 反转，得到正序的二进制串
return tmp == s; // 比较备份（逆序）与反转后（正序），若相等则是回文
}

int main() {
cin >> n; // 读入上限 n
for (int i = 1; i <= n; i++) { // 从 1 到 n 逐一判断
if (check(i)) // 如果 i 是二进制回文数
cnt++; // 计数器加 1
}
cout << cnt << endl; // 输出结果
return 0;
}

功能分析（方法2）

• 输入处理：从标准输入读取一个正整数 n。
• 枚举判断：对 1 到 n 的每个整数 i，调用 check(i) 判断其二进制是否为回文。
• 二进制转换与回文判断：
  • check 函数通过反复取余和除以 2，将最低位转换为字符并追加到字符串 s，得到二进制串的逆序表示。
  • 将逆序串备份到 tmp，然后反转 s 得到正序串。
  • 比较备份的逆序串与反转后的正序串：若相等，则原二进制串正读反读相同，即是回文。
• 计数输出：累加满足条件的个数，最后输出 cnt。

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}