GESP3级2026年3月份编程题超详解

针对“二进制回文串”问题，我们需要计算在区间 $[1, n]$ 内，有多少个正整数的二进制表示（不含前导零）是回文串。题目给定的数据范围是 $1 \\leq n \\leq 10^5$，这要求算法的时间复杂度应控制在 $O(n \\log n)$ 或更优。

问题解构与算法分析

问题的核心在于判断一个正整数是否为二进制回文数。其标准流程为：

暴力枚举法是最直观的解法：遍历 $1$ 到 $n$ 的每个整数，执行上述两步判断，统计回文数个数。对于每个数，二进制转换和回文判定的时间复杂度为 $O(\\log n)$，总复杂度为 $O(n \\log n)$，在 $n=10^5$ 的约束下完全可行。

算法流程：

复杂度分析：

• 时间复杂度：$O(n \\log n)$。遍历 $n$ 个数，每个数的二进制位数约为 $\\log_2 n$，转换和比较操作与之线性相关。
• 空间复杂度：$O(\\log n)$。主要开销在于存储每个数的二进制字符串。

代码实现与详细注释

以下是 C++ 语言的实现代码，包含两种常见方法：使用标准库函数进行回文判断，以及手动进行回文判断。

#include <iostream>
#include <bitset>
#include <algorithm>
#include <string>
using namespace std;

// 方法一：使用标准库函数判断回文
int countBinaryPalindromes_method1(int n) {
int count = 0;
for (int i = 1; i <= n; ++i) {
// 将整数转换为二进制字符串（bitset会自动处理前导零）
string binStr = bitset<32>(i).to_string(); // 使用足够大的位数，如32
// 去除前导零：找到第一个'1'的位置
size_t firstOne = binStr.find('1');
if (firstOne != string::npos) {
binStr = binStr.substr(firstOne);
} else {
// 如果全为0（即i=0的情况，但i从1开始，所以不会进入此分支）
binStr = "0";
}
// 判断是否为回文：比较字符串与其反转
string reversedStr = binStr;
reverse(reversedStr.begin(), reversedStr.end());
if (binStr == reversedStr) {
++count;
}
}
return count;
}

// 方法二：手动判断回文（更高效，避免字符串拷贝和反转）
int countBinaryPalindromes_method2(int n) {
int count = 0;
for (int i = 1; i <= n; ++i) {
// 获取二进制表示
string binStr;
int temp = i;
while (temp > 0) {
binStr.push_back((temp & 1) ? '1' : '0');
temp >>= 1;
}
// 此时binStr是逆序的（最低位在前），需要反转一次得到正序
reverse(binStr.begin(), binStr.end());

// 手动判断回文
bool isPalindrome = true;
int left = 0, right = binStr.size() – 1;
while (left < right) {
if (binStr[left] != binStr[right]) {
isPalindrome = false;
break;
}
++left;
–right;
}
if (isPalindrome) {
++count;
}
}
return count;
}

int main() {
int n;
cin >> n;

// 两种方法任选其一
// int result = countBinaryPalindromes_method1(n);
int result = countBinaryPalindromes_method2(n);

cout << result << endl;
return 0;
}

代码要点解析：

运行示例与场景扩展

以样例输入 n = 15 为例，程序的执行过程如下：

为了更深入地理解二进制回文数的分布，我们可以分析其数学特性。二进制回文数与对称性紧密相关。对于一个 $k$ 位的二进制数，如果它是回文数，那么其二进制串的前 $\\lceil k/2 \\rceil$ 位决定了整个数。例如，所有3位二进制回文数为： 101(5)、 111(7)。所有4位二进制回文数为： 1001(9)、 1111(15)。这种特性可以用于构造法生成所有不超过 $n$ 的二进制回文数，从而将时间复杂度降低到 $O(\\sqrt{n} \\log n)$ 或更好，但这超出了本题暴力法的范畴。

算法思想总结与扩展

本题是数制转换与字符串处理的结合，主要考查以下能力：

扩展思考：

• 更大数据范围：如果 $n$ 增大到 $10^9$ 甚至更大，暴力枚举将不可行。此时需要利用二进制回文数的构造规律进行计数。例如，可以按二进制位数分组，对于长度为 $len$ 的二进制回文数，其前一半（$\\lceil len/2 \\rceil$ 位）可以任意取（但不能全为0），从而计算出该长度下的回文数个数，再累加所有长度不超过 $\\lfloor \\log_2 n \\rfloor + 1$ 且对应数值不超过 $n$ 的回文数。
• 其他进制回文：问题可以推广到判断任意进制（如十进制、八进制、十六进制）下的回文数。只需将转换基数从2改为目标进制即可。
• 同时是多种进制回文的数：寻找同时是二进制和十进制回文的数（如1, 3, 5, 7, 9, 33, 99等）。这需要多一层进制转换和回文判断。

通过解决此题，可以巩固循环、位运算、字符串操作等基础编程技能，并为处理更复杂的数论与字符串结合问题打下基础。