BZOJ2186: [Sdoi2008]沙拉公主的困惑
BZOJ4236~4247

BZOJ 4404: [Neerc2015]Binary vs Decimal

YYY posted @ 2016年1月22日 21:58 in 算法竞赛 with tags 哈希 高精度 搜索 , 1539 阅读
_THIS_IS_START_OF_ARTICLE_
经过了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;
}

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

_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter