bzoj 4404: [Neerc2015]Binary vs Decimal

做多项式做到自闭。。
感觉我智商实在是不够啊。。
于是开个题玩一下。。

挺简单的一个题
接下来第几位都是从低位往高位数
简单分析以后可以发现，10进制第i位，对应的二进制一定第i位也是1，然后剩下都是0，这个不难证明
假设我们一位一位填
于是得到合法的充分必要条件
就是我们填到第i位，第i位的二进制是0
当然，前i-1位肯定是合法的
然后就没有了
实现的话，可以维护一个队列，合法的数丢到队列里面
慢慢扩展就可以了
容易发现复杂度是$O(n?|S|)$的，S表示答案长度
估算一下，开了个1000就过了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
using namespace std;
const int N=10005;
const int SIZ=1000;
int n;
int s[N][SIZ+5];
int now[SIZ+5];
int len;//长度是多少 
int id=-1;
queue<int> q,q1,q2;
void update ()//更新now 
{
    for (int u=SIZ;u>=0;u--)	if (now[u]==1)	{
    now[u]=0;now[u+1]++;now[u+3]++;}for (int u=0;u<=SIZ;u++)	{
    now[u+1]=now[u+1]+now[u]/2;now[u]&=1;}
}
void print (int x)
{
    printf("YES:%d\n",x);bool tf=false;for (int u=SIZ;u>=0;u--){
    if (s[x][u]==1) tf=true;if (tf) printf("%d",s[x][u]);}printf("\n");
}
int main()
{
    scanf("%d",&n);if (n==1) {
    printf("1\n");return 0;}n--;id++;s[id][0]=0;id++;s[id][0]=1;q.push(0);q.push(1);now[0]=1;len=0;while (true){
    update();len++;//现在要检查第几位了f//printf("YES\n");/*for (int u=0;u<=SIZ;u++) printf("%d",now[u]);printf("\n");*/while (!q.empty()){
    int x=q.front();q.pop();if (s[x][len]==1) 	continue;//这一位填不填都是GGq1.push(x);n--;id++;for (int u=0;u<=SIZ;u++)	s[id][u]=s[x][u]+now[u];for (int u=0;u<=SIZ;u++)	{
    s[id][u+1]=s[id][u+1]+s[id][u]/2;s[id][u]%=2;}if (n==0)	{
    for (int u=len;u>=0;u--) printf("%d",s[id][u]);return 0;}q2.push(id);}while (!q1.empty())	{
    q.push(q1.front());q1.pop();}while (!q2.empty()) {
    q.push(q2.front());q2.pop();}return 0;
}