比较奇怪的一个枚举题。
注意到10=2*5，所以10^k的二进制表示一定恰好在末尾有k个0。 考虑从小到大去填这个十进制数。 填的时候记录一下当前的二进制表示。 每次尝试去填0或者10^k。 如果要填下一位的时候发现它的二进制表示已经为1的话，停止扩展。 因为： 如果这一位填0，由于后面填的数末尾的0>k不会影响这一位，无法是其与二进制后缀相同。 如果这一位填1，必然产生进位，同理，也无法与其二进制后缀相同。 考虑这样做的复杂度。 考虑每一个答案。把它扩展出来最多利用了k步中间状态，k为其长度，加上高精度的复杂度，最终复杂度为O(nk^2)。#include#include #include #include #include #include #include #include #include #define N 22000#define L 2200#define eps 1e-7#define inf 1e9+7#define ll long longusing namespace std;inline int read(){ char ch=0; int x=0,flag=1; while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*flag;}struct big{ int len,a[L]; big() { len=1; memset(a,0,sizeof(a)); } void print() { for(int i=len;i>=1;i--)printf("%d",a[i]); }};big operator+(big a,big b){ big ans; ans.len=max(a.len,b.len); for(int i=1;i<=ans.len;i++) { ans.a[i]+=a.a[i]+b.a[i]; ans.a[i+1]+=(ans.a[i]>>1); ans.a[i]&=1; } if(ans.a[ans.len+1])ans.len++; return ans;}big operator*(big a,int b){ big ans=a; for(int i=1;i<=ans.len;i++)ans.a[i]*=b; for(int i=1;i<=ans.len;i++) { ans.a[i+1]+=ans.a[i]>>1; ans.a[i]&=1; } while(ans.a[ans.len+1]) { ans.len++; ans.a[ans.len+1]+=ans.a[ans.len]>>1; ans.a[ans.len]&=1; } return ans;}big k,v,q[N],f[N];int main(){ int n=read(),i,l=1,r=1,t=1,cnt=0,tot=1; k.a[1]=v.a[1]=1;q[1].a[1]=0;f[1].a[1]=0; for(;;l=r+1,r=tot,t++) { for(i=l;i<=r;i++) if(!q[i].a[t])q[++tot]=q[i],f[tot]=f[i]; for(i=l;i<=r;i++) if(!q[i].a[t]) { q[++tot]=q[i]+k;f[tot]=f[i]+v,cnt++; if(cnt==n){f[tot].print();return 0;} } v=v*2;k=k*10; } return 0;}