题目大意:
给一个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了吧。。
各种小技巧还是挺有意思的。