》》》点我查看「视频」详解》》》
[GESP202412 四级] Recamán
题目描述
小杨最近发现了有趣的 Recamán 数列，这个数列是这样生成的：
- 数列的第一项 a 1 a_1 a1 是 1 1 1；
- 如果 a k − 1 − k a_{k-1}-k ak−1−k 是正整数并且没有在数列中出现过，那么数列的第 k k k 项 a k a_k ak 为 a k − 1 − k a_{k-1}-k ak−1−k，否则为 a k − 1 + k a_{k-1}+k ak−1+k。
小杨想知道 Recamán 数列的前 n n n 项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
输入格式
第一行，一个正整数 n n n。
输出格式
一行， n n n 个空格分隔的整数，表示 Recamán 数列的前 n n n 项从小到大排序后的结果。
样例 #1
样例输入 #1
5
样例输出 #1
1 2 3 6 7
样例 #2
样例输入 #2
8
样例输出 #2
1 2 3 6 7 12 13 20
提示
样例解释
对于样例 1， n = 5 n=5 n=5：
- a 1 = 1 a_1=1 a1=1；
- a 1 − 2 = − 1 a_1-2=-1 a1−2=−1，不是正整数，因此 a 2 = a 1 + 2 = 3 a_2=a_1+2=3 a2=a1+2=3；
- a 2 − 3 = 0 a_2-3=0 a2−3=0，不是正整数，因此 a 3 = a 2 + 3 = 6 a_3=a_2+3=6 a3=a2+3=6；
- a 3 − 4 = 2 a_3-4=2 a3−4=2，是正整数，且没有在数列中出现过，因此 a 4 = a 3 − 4 = 2 a_4=a_3-4=2 a4=a3−4=2；
- a 4 − 5 = − 3 a_4-5=-3 a4−5=−3，不是正整数，因此 a 5 = a 4 + 5 = 7 a_5=a_4+5=7 a5=a4+5=7。
a 1 , a 2 , a 3 , a 4 , a 5 a_1,a_2,a_3,a_4,a_5 a1,a2,a3,a4,a5 从小到大排序的结果为 1 , 2 , 3 , 6 , 7 1,2,3,6,7 1,2,3,6,7。
数据范围
对于所有数据点，保证 1 ≤ n ≤ 3 000 1\le n\le 3\, 000 1≤n≤3000。
AC_Code
#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
int w[N];int main()
{int n;cin >> n;w[1] = 1;set<int> s;s.insert(1);for(int i = 2; i <= n; i ++){int x = w[i - 1] - i;if(x > 0 && s.find(x) == s.end()) w[i] = x;else w[i] = w[i - 1] + i;s.insert(w[i]);}sort(w + 1, w + n + 1);for(int i = 1; i <= n; i ++)cout << w[i] << " ";return 0;
}
》》》点我查看「视频」详解》》》
