2026年3月GESP真题及题解（C++三级）：二进制回文串
题目描述
对于一个正整数 
，我们将其转换为不含前导零的二进制表示，如果这个二进制序列从左向右读与从右向左读完全相同，则称该数为二进制回文数。例如，
的二进制表示为 
，是二进制回文数；
的二进制表示为 
，不是二进制回文数。
你的任务是：给定一个正整数 
，计算在 
到 
的范围内二进制回文数的数量。
输入格式
输入一行，包含一个正整数 
。
输出格式
输出一行，包含一个数，表示在 
到 
的范围内二进制回文数的数量。
输入输出样例 1
输入 1
15输出 1
6说明/提示
样例解释
样例 1 中，
到 
范围内 
、
、
、
、
、
是二进制回文数。
数据范围
。
思路分析（方法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 是否为二进制回文数boolcheck(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;}intmain(){cin >> n; // 读入上限 nfor (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 是否为二进制回文数boolcheck(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; // 比较备份（逆序）与反转后（正序），若相等则是回文}intmain() {cin >> n; // 读入上限 nfor (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;intmain(){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;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return 0;}
