说有一个序列，a[0] = 0 ;对于 m > 0，a
= a − m，如果 a 是正的并且没有出现在序列中，否则 a = a + m。问序列的第 k 项是多少。
貌似不复杂，不过得用位操作来检查元素是否存在过，不能直接查找。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | /* * http://blog.csdn.net/cugbliang/archive/2008/08/05/2773788.aspx * */ #include<stdio.h> #include<string.h> int a[500001]; char have[376600]; const static int mark[]={0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80}; int main() { memset(have,0,sizeof(have)); a[0]=0; have[0] = true; int t,i; for(i=1; i <= 500000; i++) { t = a[i-1] - i; if(t > 0 && !(have[t/8] & mark[t%8])) { a[i] = t; have[t/8] |= mark[t%8]; } else { a[i] = a[i-1] + i; have[a[i]/8] |= mark[a[i]%8]; } } int n; while(1) { scanf("%d",&n); if(n==-1) break; printf("%d\n",a[n]); } return 0; } |
Related posts(相关文章):