题解 P1826 【猴子选大王数据再加强版】

asdfo123 · 2020-10-19 08:08:15 · 题解

约瑟夫问题典型例题

这类问题模板：

n 个人标号 1~ n。逆时针站一圈，从1号开始，每一次从当前的人逆时针数m个，然后让这个人出局。问最后剩下的人是谁。

我们思考，有 N 个猴子，如果现在一个猴子出列，那么剩下的猴子就变成了 (n-1) 个猴子数数的子问题。

我们设 f_i 为 i 个猴子数数选出的大王编号，那么由于新的子问题要从下一个猴子开始数，编号要加上 m

那么可以得到递推式子：

这样是编号从0开始的，我们想要编号从１开始

那么：

最后别忘了要从 a开始统计最大值...

代码：

#include <bits/stdc++.h>
using namespace std;
int f[1000010];
int vis[1000010];
int a,b,m;
int main()
{
    scanf("%d%d%d",&a,&b,&m);
    f[1] = 1;
    int ans = 0;
    for(int i = 1;i <= b;i++)
    {
        f[i] = (f[i-1]+m-1)%i+1;
        if(i>=a)
        {
            vis[f[i]]++;
            ans = max(ans,vis[f[i]]);
        }
    }
    printf("%d\n",ans);
    for(int i = 1;i <= b;i++)
    {
        if(vis[i] == ans) printf("%d ",i);
    }
    return 0;
}