BZOJ 4404: [Neerc2015]Binary vs Decimal
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_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;
}
-------------------------------------------------------------
评论 (0)
