ZOJ 2421 Recaman's Sequence

题目大意：

定义a^m为 a^m = a^(m-1) - m 如果a^m 为正且没有出现过。否则a^m = a^(m-1) + m 。给你k，让你求a^k

思路：

打表。

k最大为50万，而a[500000]<63万，故我们开个数组记录是否出现过即可。

#include
  
   
const int MAXK=500000+2;
const int MAXN=630000;
int a[MAXK];
bool exist[MAXN]={0};
int main()
{
	a[0]=0;
	exist[0]=1;
	for(int i=1;i
   
    0 && !exist[ a[i-1]-i ]) a[i]=a[i-1]-i; else a[i]=a[i-1]+i; exist[ a[i] ]=1; } //printf(%d ,a[500000]); 62W int k; while(~scanf(%d,&k),k!=-1) { printf(%d ,a[k]); } return 0; }