csp 201712-2 游戏 暴力，附：约瑟夫环的递推

中问题竟然愚蠢的看错题了。中文读题能力还不如英文，有待提升。

所以这道题用普通的数组模拟操作就可以了。总之跟暴力模拟的约瑟夫环没什么区别。

可以用next数组模拟指针做数据结构，但是数据范围不大的情况下不建议这么写，维护一个指针环写起来还是比较麻烦的。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
bool survive[MAXN];
 
int solve(int n, int k)
{
    for(int i = 0; i < n; i++)
    {
        survive[i] = true;
    }
    int cnt = 0, snum = n;
    int idx = -1;
    while(snum)
    {
        idx = (idx + 1) % n;
        if(survive[idx] == true){
            cnt++;
            if(cnt % k == 0 || cnt % 10 == k){
                survive[idx] = false;
                //printf("%d\n", idx+1);
                snum--;
            }
        }
        if(snum == 1)break;
    }
    for(int i = 0; i < n; i++)if(survive[i] == true)return i;
}
int main()
 
{
    int n, k;
    scanf("%d%d", &n, &k);
    int ans = solve(n, k);
    printf("%d\n", ans+1);
    return 0;
}

但是突然想到比得十分GG的蓝桥杯国赛，必须要记录一下约瑟夫环的标准数学（找规律）解法。

将k固定，设解ANS[n,k] = ans(n)

具有m个数的m约瑟夫环中，删除一个数之后，相当于重新标号后的m-1约瑟夫环问题。

设从a(1)开始的m约瑟夫环答案为ans(m) = s，在m+1约瑟夫环中，由于经历了重新标号，m中的标号a(i)应该为a((k+i)%(m+1)) ,所以答案下标也要从s移动到(s+k)%(m+1).

公式：ans(1) = 1, ans(m+1) = (ans(m)+k)%(m+1)。代码如下：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
//标准约瑟夫环，非此题题解
int main()
{
    int n, k;
    int i, s = 0;
    scanf("%d%d", &n, &k);
    for (i = 2; i <= n; i++)
    {
        s = (s + k) % i;
        //printf("%d\n",s+1);
    }
    printf ("%d\n", s+1);
}