sgu 108[卡内存什么的]

题目大意:
给一个n,另d(n)= n + sum{digit_i}(for i = 1 to length(n), digit_i is n's no.i digit)
若y = d(n),则n就是y的generator。
若某个数没有generator,那么这个数就叫self number。
要求:给你一个N[1,10^7],一个k[1,5000]
k个数,s1...sk。
让你求出[1,N]中有多少个self numbers。并输出k个a[si],即第si个self number。保证si不大于N中self number的数量。

做法,本来很水的一题,用类似筛法的思想筛一遍就搞定了。
但是因为当年的SGU很穷,所以没钱买内存,于是乎内存只给了4M。必须用点ws的方法了。

10^7的bool数组大小约为9.5M,10^6的int数组约为4M内存(10^7中一共有977xxx个self numbers),省内存就要从两方面入手。

节省int数组的开销,即不存储这个数组,而是把输入的si排序,当扫描到对应的si的时候,直接标记下来。注意wa点:si不一定有序,且有可能重复。
节省bool数组的开销:
法1:位压缩,bitset或者手写位运算均可。
法2:滚动数组。由于d(n) <= n + 9*7在10^7的范围内。所以只需开一个64大小的滚动数组即可。
实现:
if(vis[i%64])//if(vis[i&63])
{
//blabla
}
vis[i%64] = true;//这时候i已经扫描过去了,所以对于下一个等于i%64的i,默认是true的
vis[d(i)%64] = false;//筛掉d(i)

虽然我莫名其妙的G++WA on testcase9,C++AC了吧。。

各种小技巧还是挺有意思的。

posted on 2012-03-16 20:35 BUPT-[aswmtjdsj] @ Penalty 阅读(408) 评论(0)  编辑 收藏 引用 所属分类: 乱搞


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜