WC结束了,来补一下这题的题解
首先感谢SC神犇YYY(第一个AC此题的神犇)教我做法
再感谢教YYY做法的Claris大爷
首先,我们发现一个性质,一个合法的数的后缀必定是合法的,所以我们就可以bfs了,往合法的数的最高位加0或1
只有最高位是1的数才有可能是答案
YYY大爷告诉我们,并且不难证明任何时候队列中以0开头的数字数量小于等于以1开头的数字数量,并且每次进入合法节点最多只会生成一个不合法数字,因此整个搜索是O(n*处理每个节点的时间)的
对于队列里的每个数,记录3个东西,十进制下的hash值,十进制长度len,二进制后len位
同时维护当前10^len的二进制,由于是BFS,所以len只增不减
最后有一个问题,队列里的元素不是有序的。这也很好办,对于相同长度的序列,只需要先全部加0,再全部加1
具体细节可以看我的代码
窝的代码是目前为止AC代码中最短的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define N 23333
#define L 170
#define P 1000000009 using namespace std;
inline void multiply(int *a,int b){
int k=0;
for (int i=1;i<=a[0];++i){
a[i]=a[i]*b+k;
k=a[i]>>1;
a[i]=a[i]&1;
}
for (;a[0]<165&&k;k=k>>1) a[++a[0]]=k&1;
} inline void add(int *a,const int *b){
a[0]=max(a[0],b[0]);
int k=0;
for (int i=1;i<=a[0];++i){
a[i]+=b[i]+k;
k=a[i]>>1;
a[i]=a[i]&1;
}
for (;a[0]<165&&k;k=k>>1) a[++a[0]]=k&1;
} inline int gethash(int *a,int len){
int ret=0;
for (int i=1;i<=len;++i)
ret=((ll)ret*233%P+a[i])%P;
return ret;
} void print(int *a,int len){
for (int i=len;i;--i) printf("%d",a[i]);
puts("");
} struct node{
int hash,len;
int b[L];
};
node q[N];int qh,qt,lastqh,lastqt;
int rank;
int t[L]; int main(){
scanf("%d",&rank);--rank;
if (!rank){puts("1");return 0;}
lastqh=qh=0;lastqt=qt=2;
q[1].len=1;q[1].hash=0;
q[1].b[0]=1;q[1].b[1]=0;
q[2].len=1;q[2].hash=1;
q[2].b[0]=1;q[2].b[1]=1;
t[0]=1;t[1]=1;
for (;;lastqh=qh,lastqt=qt){
multiply(t,10);
for (int k=0;k<2;++k){
qh=lastqh;
while (qh<lastqt){
q[++qt]=q[++qh];
++q[qt].len;
q[qt].hash=((ll)q[qt].hash*233%P+k)%P;
if (k) add(q[qt].b,t);
if (q[qt].hash!=gethash(q[qt].b,q[qt].len)) --qt;
else if (k) --rank;
if (!rank){
print(q[qt].b,q[qt].len);
return 0;
}
}
}
}
return 0;
}