最新消息:点击查看大S的省钱秘笈

POJ 2081 Recaman’s Sequence C++版

POJ题解 Slyar 2236浏览 1评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

水题,典型的空间换时间…

Description

The Recaman’s sequence is defined by a0 = 0 ; for m > 0, am = am−1 − m if the rsulting am is positive and not already in the sequence, otherwise am = am−1 + m.
The first few numbers in the Recaman’s Sequence is 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9 …
Given k, your task is to calculate ak.

Input

The input consists of several test cases. Each line of the input contains an integer k where 0 <= k <= 500000.
The last line contains an integer −1, which should not be processed.

Output

For each k given in the input, print one line containing ak to the output.

Sample Input

7
10000
-1

Sample Output

20
18658

Slyar:没难度,打表就行了,标记数组开到260W就差不多了,我才懒得搜索…

#include 

using namespace std;

char ext[2600000] = {0};
int a[500001];

void reset()
{
    int i;
    a[0] = 0;
    ext[0] = 1;
    for (i = 1; i <= 500000; i++)
    {
        a[i] = a[i-1] - i;
        if (a[i] < 0 || ext[a[i]])
        {
            a[i] = a[i-1] + i;
        }
        ext[a[i]] = 1;
    }
}

int main()
{
    int k;
    reset();
    while(cin >> k && k != -1)
    {
        cout << a[k] << endl;
    }
    //system("pause");
    return 0;
}

转载请注明:Slyar Home » POJ 2081 Recaman’s Sequence C++版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (1)