425      iPhone_iPad_Mac_apple

poj 2081 Recaman's Sequence【hash】

題目意思不難理解就是第m個位置的數是根據第m-1位置的數推出來的如果a[m-1]-m>0，並且a[m-1]-m在前麵的序列中沒有出現過那麼a[m] = a[m-1]-m否則a[m] = a[m-1]+m

另外唯一需要注意的一點就是hash數組開大一點。

//打表

#include <stdio.h>
#include <iostream>

using namespace std;

const int MAXN=500003;

int a[MAXN]={0};
bool hash[10000000]={false};


void prepare()
{
	//預處理表
	int i;
	for(i=1;i<MAXN-1;i++)
	{
		if (a[i-1]-i>0 && hash[a[i-1]-i]==false)
		{
			a[i]=a[i-1]-i;

			//改變hash值
			hash[a[i-1]-i]=true;
		}

		else
		{
			a[i]=a[i-1]+i;

			//改變hash值
			hash[a[i-1]+i]=true;
		}
	}
}



int main()
{
	int k;

	prepare();

	while(~scanf("%d",&k) && k!=-1)
		printf("%d\n",a[k]);


	return 0;
}

最後更新：2017-04-03 05:39:41

  上一篇： 【Tsinghua】麵試(Interview)

  下一篇： linux c 文件打開並創建代碼分析