题解 [ARC127C] Binary Strings

cjh20090318 · 2024-08-19 20:28:16 · 题解

题意

给出 n,x，请求出二进制下 [1,2^n-1] 中字典序第 x 小的数是什么。

分析

从样例观察出每一个数的第一个字符都是 1，然后画出 n=3 的树。

节点即第 x 小的终止位置，边权从上到下依次表示二进制位。

顺着树从上往下，设当前节点在第 i 层（1 为第 1 层），依次判断：

• 当 x=1 时，跳出循环。
• 如果 x > 2^{n-i} 时，x \gets x-2^{n-i}，进入右子树并输出 1。
• 否则 x \gets x-1，进入左子树并输出 0。

用 std::bitset 模拟即可，具体实现看代码。

代码

//the code is from chenjh
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define MAXN 1000005
using namespace std;
int n,m;
char s[MAXN];
bitset<MAXN> b;
int main(){
    scanf("%d ",&n);
    int c=0;//维护 popcount。
    scanf("%s",s),m=strlen(s),reverse(s,s+m);//翻转最低位和最高位。
    for(int i=0;i<n;i++) c+=(b[i]=s[i]?s[i]^'0':0);
    putchar('1');
    for(int i=n-1;i>=0;--i){
        if(c==1&&b[0]) break;//只有 1 个位置为 1 且为第 0 位，即说明 x=1。
        else if(b[i]&&c>1) b[i]=b[i]^1,--c,putchar('1');//严格大于（不止该位为 1）。
        else{
            int x=b._Find_first();//找到最低位为 1 的。
            for(int i=0;i<x;i++) b[i]=1,++c;//减 1 操作。
            b[x]=0,--c;
            putchar('0');
        }
    }
    return 0;
}