$Acwing4400$.玩游戏

一、模拟

分析

从第一个人开始，每次向后向数$x$个人，最后被数到的人被淘汰出局
模拟一个环，$i$次操作后操作后剩余的人数实际上是$n-i$，每次要向后数的人数$x$对$(n-i+1)$取模就可以将操作的数始终控制在环内$n$个人，要注意在算第$n$个人的下一个人时不能直接+ +，要直接置成1。如果当前向后数的人已经被淘汰了，那么要给$x$++(这个人不算，要跳过这次计数)

步骤总结

① $%t=(n - i + 1)$算出这一次在当前有效人数里要往后数多少个
② 往后数$t$个人(注意这个$while(x -$$-)$的写法)
③ 往后数$t$这个人被标记淘汰后，要将当前数的权利往后给下一个有效的人

#include<bits/stdc++.h>
using namespace std;
bool st[1010];
int main()
{
    int n, k, cur = 1; cin >> n >> k;
    for (int i = 1; i <= k; i ++)
    {
        int x; cin >> x;
        x %= (n - i + 1);  // 第n个人的下一个是1，n-i+1是因为当前已经去掉了i-1个人，还剩n-i+1个
        while (x --)  // 计数x个未被淘汰的人
        {
            if (cur == n) cur = 1;  // 回头
            else cur ++;
            if (st[cur]) x ++;  // 如果这个人已经被淘汰了，那么要跳过
        }
        st[cur] = true;
        cout << cur << ' ';
        while (st[cur])  // 将开始权放到下一个没被淘汰的人
            if (cur == n) cur = 1;  // 第n个人的下一个是1
            else cur ++;
    }
    return 0;
}

二、$dp$推公式

$Krahets$题解，太秀了…
下面这段中的关键是要注意是 编号对应关系（这里是包括当前的人往后数$m$个，所以$m$要减$1$再模$n$，注意和上面玩游戏的题对比，玩游戏的是不包括当前人往后数$m$个）
即$[n-1,m]$问题中的编号$0$的数字，对应的是$[n,m]$问题中的编号$t$，同理$[n-1,m]$问题中的编号$1$的数字，对应的是$[n,m]$问题中的编号$t+1$，那么$[n-1,m]$问题中最后剩下的唯一一个数字$f(n-1)$，对应的是$[n,m]$问题中的编号$(f(n-1)+t)%n$，所以可以得到下面的递推关系式

由于玩游戏的题并不是要进行至只剩一人，同时每一轮往后数的个数不一样，因此$f[1]$可能推不出$f[2]$、$f[3]$，因为长度为2时往后数的人数未知
如果仍然是进行至只有一人，则还是可以找$[n-1, a[i-1]]$问题与$[n,a[i]]$问题的关系来找递推式