题解：P12191 [蓝桥杯 2025 省研究生组] 01 串

· · 题解

有被恶心到。但是其实不太难。

题意：将 0,1,2,3 \dots 的二进制顺次排列拼接为一个 01 串，即 011011100101110111\dots。给定 x，求这个串前 x 位 1 的个数。1\le x\le10^{18}。

我们先把第一位的 0 扔掉，考虑第 2 到 x 位。这一串序列显然是由一些完整的数字的二进制和一个（也可能没有）不完整的数字组成的。

考虑暴力怎么做。我们可以枚举完整的数字，计算它们的二进制中 1 的个数（可以使用 __builtin_popcount() 函数实现），最后单独计算剩下的那个不完整的数字。代码如下：

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    long long n,sum=0,ans=0,i=1;  //sum用于记录当前枚举到了第几位，i为枚举到了第几个完整的数字，ans记录答案
    cin>>n;
    n--;  //把第一位的0扔掉
    while(sum<n){
        sum+=floor(log2(i))+1;
        ans+=__builtin_popcount(i);
        i++;
    }
    i--;
    long long x=sum-n;
    cout<<ans-__builtin_popcount(i)+__builtin_popcount(i>>x);
    return 0;
}

这样显然无法通过此题。分析代码，发现瓶颈在于枚举有多少个完整的数字和记录答案（也就是枚举计算代码中的 i 和 ans）。分别考虑如何优化。

先来考虑，如果我们已经知道了完整数字的个数，如何计算答案。也就是已知 k，如何计算前 k 个正整数的二进制下 1 的个数之和。我们使用暴力来打表，发现前 i 个正整数二进制下 1 的个数之和是这样一个序列：

1 2 4 5 7 9 12 13 15 17 20 22 25 28 32 33 ...

设这个序列的第 i 项为 a_i。手动找规律，或者丢到 OEIS 上，发现 a_{2n+1}=2a_n+n+1，当然也有别的求法，在这里或者另外的题解有介绍。那么我们可以写出这样一个函数来递归求解 a_x：

long long get(long long x){
    if(!x){
        return 0;
    }
    if(x&1){
        return 2*get(x/2)+x/2+1;
    }
    else{
        return 2*get(x/2)+x/2+1-__builtin_popcountll(x+1);
    }
}

显然，由于每次 x 变为原来的一半，这个函数时间复杂度为 O(\log x)。

因此前面的暴力可以优化（实际上并没有，只是向正解贴近）为下面这样：

#include<iostream>
#include<cmath>
using namespace std;
long long get(long long x){
    if(!x){
        return 0;
    }
    if(x&1){
        return 2*get(x/2)+x/2+1;
    }
    else{
        return 2*get(x/2)+x/2+1-__builtin_popcountll(x+1);
    }
}
int main(){
    long long n,sum=0,ans=0,i=1;
    cin>>n;
    n--;
    while(sum<n){
        sum+=floor(log2(i))+1;
        i++;
    }
    i--;
    long long x=sum-n;
    cout<<get(i)-__builtin_popcountll(i)+__builtin_popcountll(i>>x);
    return 0;
}

虽然实际上复杂度还是不足以通过，但是我们的瓶颈少了一个。现在我们只需要设法快速求解完整的数字个数即可。

注意到在一段连续的区间内，所有数的二进制长度是相同的。这很好理解，与十进制类似，连续一段数字的位数是相同的。想办法利用这一点。考虑对原 01 序列再次分段，将长度相同的分为一大段。那么由于每次到 2^n 会进一次位，第 i 大段的长度为 2^{i}-2^{i-1}=2^{i-1}，这一大段每个数二进制长度为 i，所以这一大段总长度为 i\times 2^{i-1}。与前面类似，我们枚举完整的大段即可。接下来考虑不完整的大段。不完整的大段中剩下的与整段类似，也是由一些完整的数字和零个或一个不完整数字组成的。不同的是，这些完整数字的位数都是相同的，我们可以轻松地直接求出完整数字的个数，再用与前面暴力相同的方式算上不完整的数字即可。

综上，我们可以写出下面的 AC 代码：

#include<iostream>
#include<cmath>
using namespace std;
long long get(long long x){
    if(!x){
        return 0;
    }
    if(x&1){
        return 2*get(x/2)+x/2+1;
    }
    else{
        return 2*get(x/2)+x/2+1-__builtin_popcountll(x+1);
    }
}
int main(){
    long long n,sum=0,ans=0,i=1;
    cin>>n;
    n--;
    //此处i枚举的是大段
    while(sum<n){
        sum+=i*(1ll<<(i-1));
        i++;
    }
    i--;
    sum-=i*(1ll<<(i-1));
    i--;
    long long x=0;  //通过大段数量统计数字个数
    for(long long j=0;j<i;j++){
        x+=(1ll<<j);
    }
    sum=n-sum;
    i++;
    ans=get(x+sum/i);
    x+=sum/i+1;
    long long r=i-sum%i;
    cout<<ans+__builtin_popcountll(x>>r);
    return 0;
}

时间复杂度约为 O(\log x)，可以通过本题。