解题思路

问题分析：

Recaman序列的生成规则要求每一步根据前一个值和当前索引来决定下一步的值。关键在于确保新生成的值是唯一的且为正数。

关键点：

使用数组$s$存储序列的值。

使用标记数组$num$来记录已经出现过的值，避免重复。

对于每个$m$，先尝试减去$m$，如果结果为负或已存在，则改为加上$m$。

算法选择：

预处理（打表）： 由于$k$的范围较大（$0$ ≤ $k$ ≤ $500000$），直接预处理整个序列，存储所有可能的$aₖ$值，查询时直接返回结果。

标记数组：

使用一个足够大的数组$num$来标记已经生成的序列值，确保唯一性。

优化：

预处理阶段的时间复杂度为O(n)，其中$n$为$500000$，可以接受。

查询阶段的时间复杂度为O(1)，直接访问预处理后的数组。

解题方法

初始化：

数组$s$用于存储序列，初始时$s[0]$ = $0$。

标记数组$num$用于记录已经出现的值，初始时$num[0]$ = $1$。

生成序列：

对于每个$i$从$1$到$500000$：

计算$s[i]$ = $s[i-1]$ - $i$。

如果$s[i]$为负数或$num[s[i]]$已被标记，则重新计算$s[i]$ = $s[i-1]$ + $i$。

标记$num[s[i]]$ = $1$。

处理查询：

读取输入$k$，直到遇到$-1$为止。

对于每个$k$，直接输出预处理好的$s[k]$。

C++代码实现：

#include<stdio.h>
int s[500010]={0},num[5000010]={0};//初始化 
int main()
{
    int n,i,j;
    s[0]=0;
    num[0]=1;//标记数组 
    for(i=1;i<500010;i++)//打表 
    {
        s[i]=s[i-1]-i;
        if(s[i]<0||num[s[i]])//出现过 
            s[i]=s[i-1]+i;
        num[s[i]]=1;//标记 
    }
    while(scanf("%d",&n)&&n!=-1)
        printf("%d\n",s[n]);
    return 0;
}