BZOJ 4404: [Neerc2015]Binary vs Decimal

BZOJ4404
经过了Claris大爷的指导之后做出来的...
sto Claris
-------------------------------------------------------------
 
首先不难证明对于任意一个合法的数字,它的后缀都是合法的
因此考虑搜索:每次获得一个合法数字后,把1或0加到其前面,并判断是否合法,如果合法就加入待搜索的序列
因为要生成第k个,因此第i个搜索到的数字要和它是第几个有关系最好
考虑BFS,BFS可以保证搜索序列按长度排序,但没有按大小排序
打表发现长度小于等于第1w个合法数字的数字只有1w+100个左右,因此可以把前1w+100个都搜出来,然后排序之后直接输出第n个(要注意的是,以0开头的是没有意义的,因此只记录以1开头的,并且不难证明任何时候队列中以0开头的数字数量小于等于以1开头的数字数量,并且每次进入合法节点最多只会生成一个不合法数字,因此整个搜索是O(n*处理每个节点的时间)的)
现在考虑搜索的细节
 
打表发现第1w个数的长度不超过200,令Q=200
如果搜索的每一次处理是O(Q)的就是可以接受的
 
考虑有哪些操作是要做的:
①.在开头加入一个数字
②.判断是否合法
 
现在考虑维护两个整数:
h:十进制表示的哈希值
k:十进制表示的位数
以及两个高精度数:
B:当前数字的二进制表示
T:10^k的二进制表示
 
考虑之前说的两个操作:
①.在开头加入一个数字:
令k=k+1(O(1))
维护一下h(O(1))
令T=T*10(高精度*低精度,O(Q))
令B=B+T(高精度+高精度,O(Q))
②.判断是否合法
获得B的低k位的哈希值h2(O(Q))
比较h和h2(O(1))
 
这样就把上面说的操作O(Q)实现了
 
然后可以用bitset强行降一点复杂度,最后的时间复杂度是O(n*Q/log)
 
话说这个题我本机最大数据100+ms过为啥交到BZOJ上跑了5000+ms啊摔
-------------------------------------------------------------

#include <stdio.h>

#include <bitset>

//#include <queue>

#include <algorithm>

#include <time.h>

 

#define DEB(s...) fprintf(stderr,s);

 

const int N = 10000;

const int Q = 10100;

const int Claris = 200;//伟大的Claris教导我们:这个题的答案不会超过200位 

 

typedef std::bitset<Claris + 10> Bit;

typedef unsigned int Int;

 

struct node

{

    Int h;

    int k;//10

    int p;//2

    Bit ten;//10^k

    int tp;

    Bit bit;

};

 

const Int K = 3u;

 

Int pow[N + 10];

 

//std::queue<node> queue;

 

bool can(const node & d)

{

    Int h = 0;

    for(int i = d.k;i >= 0;i--)

    {

        h *= K;

        h += d.bit[i];

    }

    return h == d.h;

}

 

void add(Bit & a,Bit & b,int & k1,int k2)

{

    int ad = 0;

    if(k2 > k1)

        k1 = k2;

    if(k1 > Claris)

    	k1 = Claris;

    for(int i = 0;i <= k1;i++)

    {

        ad += a[i];

        ad += b[i];

        a[i] = (ad & 1);

        ad >>= 1;

    }

    while(ad && k1 <= Claris)

    {

        k1 ++;

        a[k1] = (ad & 1);

        ad >>= 1;

    }

}

 

void mul10(node & d)

{

    Bit a = d.ten << 1;

    d.ten <<= 3;

    d.tp += 3;

    add(d.ten,a,d.tp,d.tp);

}

 

node bits[Q + 10];

 

const int P = 10 * Q;

 

node queue[P + 10];

void BFS()

{

    int head = 0;

    int tail = 0;

     

    node s;

    s.bit.reset();

    s.ten.reset();

    s.ten[0] = 1;

    s.h = 0;

    s.k = -1;

    s.p = -1;

    s.tp = 0;

     

    queue[tail++] = s;

 

    int tot = 0;

     

    Bit temb;

    int temp = 0;

     

    Bit temba;

    int tempa = 0;

     

    node now;

    do

    {

        now = queue[head++];

        head %= P;

         

        if(now.k >= 0 && now.bit[now.k] == 1)

        {

            if(can(now))

                bits[++tot] = now;

            else continue;

             

            if(tot == Q)

                return ;

        }

         

        now.k ++;

        temb = now.ten;

        temp = now.tp;

        mul10(now);//2进制乘10 

        temba = now.ten;

        tempa = now.tp;

        queue[tail++] = now;

        tail %= P;

         

        now.ten = temb;

        now.tp = temp;

        add(now.bit,now.ten,now.p,now.tp);

        now.h = now.h + pow[now.k];

        now.ten = temba;

        now.tp = tempa;

        if(!can(now))

        	continue;

        queue[tail++] = now;

        tail %= P;

        

        //if(tot % 1000 == 0)

        //	DEB("%d %d\n",tot,clock());

    }

    while(head != tail);

}

 

bool cmp(const node & a,const node & b)

{

    if(a.k != b.k)

        return a.k < b.k;

    for(int i = a.k;i >= 0;i--)

    {

        if(a.bit[i] != b.bit[i])

            return a.bit[i] < b.bit[i];

    }

    return false;

}

 

int main()

{

    pow[0] = 1;

    for(int i = 1;i <= N;i++)

        pow[i] = pow[i-1] * K;

     

    int n = 0;

    scanf("%d",&n);

     

    BFS();

     

    std::sort(bits + 1,bits + 1 + Q,cmp);

     

    std::unique(bits + 1,bits + 1 + Q,cmp);

     

    node r = bits[n];

     

    for(int i = r.k;i >= 0;i--)

        printf("%d",(int)r.bit[i]);

    printf("\n");

     

    return 0;

}

-------------------------------------------------------------