文章作者：姜南(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就差不多了，我才懒得搜索…
|
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 |
#include <iostream> 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; } |