| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
个人的思路: 打表看到提交的人都是0ms就过了,而且代码很短,估计是有推导等式,我没能推出来,不过采用打表通过了,跑了360ms,需要再想想好的方法了~
如果是纯粹的打表,就有点赤裸裸了,明眼人都能看出来,应该是会超时的,于是既要选择打表有保证不能超时,则需要在打表的步长上面弄点心思了,也即将如下情况转换下
int tot = 0;
for(int i = 0; tot < maxn ; ++i) {
if(yes(i)) ans[tot++] = i;
}
转化为
int tot = 0;
for(int i = 0; tot < maxn; ) {
if( yes(i) ) ans[tot++] = i;
else i = newSet(i);
}
这样,关键是newSet(i)怎么实现的?
个人是如下处理的:
令 n = d(k)d(k-1)d(k-2)...d(0)
寻找最小i使得 d(i) = d(j) where 0<= i < j <= k,然后x = d(i) = d(i)+1
这样新的值为:n=d(k)d(k-1)...d(i+1) 0 d(i-1)...d(0) + x * 10^i
不用担心x = 10,自己可以想一下
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator