Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

个人的思路: 打表

Posted by GreatAccepted at 2010-08-26 20:50:18 on Problem 2956
看到提交的人都是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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator