G3023 [GESP202603 三级] 二进制回文串 题解

知识点：二进制、回文、枚举。

解题思路

枚举1到n，用连续取末位并反向拼接的方法得到二进制反转值rev，若rev==x则计数。

为什么正确

反转逐位按二进制进制重建，等于原数恰表示其不带前导零的二进制串回文。

易错点

不要固定补齐相同位宽后再判回文；0不在枚举范围内。

复杂度

时间O(n log n)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,ans=0;
    cin>>n;
    for(int x=1;x<=n;x++) {
        int v=x,rev=0;
        while(v) {
            rev=rev*2+v%2;
            v/=2;
        }
        ans+=rev==x;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。