UVA - 1452 Jump (约瑟夫环变式)-白红宇

UVA - 1452 Jump (约瑟夫环变式)

阅读量：2135 次

发布时间：2019-04-30

本文共 1196 字，大约阅读时间需要 3 分钟。

题目大意：

给出n,m，约瑟夫环共n项，每数到m杀一个人，问剩下的倒数第3个人、倒数第2个人、倒数第1个人的编号分别是多少

题解：

因为我们都知道求约瑟夫环问题是f[1]=0, f[n]=(f[n-1]+k)%i ,所以一开始我的想法是就用同样的方法来推倒数第2个人，

f[2]=0,f[n]=(f[n-1]+k)%i ;但是得出的结果却不对，

在倒数第2局标号为1的不一定在本局出局，在m=2的情况下是这样，被样例误导了........

但是倒数第2局一定是只有编号为0和1的两个人，所以我们可以求出倒数第1个人在倒数第2局的标号，然后1-这个编号倒数第2个人在倒数第2局的编号，有了起始编号之后剩下的就是按照那个公式推了（ f[n]=(f[n-1]+k)%i）

同理，倒数第3个人在倒数第3局的编号，然后顺着退就ok了。于是我们可以求出倒数第1个和倒数第2个人在倒数第3局的编号，它们和倒数第3个人的编号一定分别是0,1,2，所以ans3=(0^1^2)^ans1^ans2;

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define max_n 10010typedef long long LL;using namespace std;int main(){    //freopen("input.txt","r",stdin);    int n,k,T;    scanf("%d",&T);    int ans1=0,ans2=0,ans3=0;    while(T--)    {        scanf("%d%d",&n,&k);        ans1=0,ans2=0,ans3=0;        for(int i=2;i<=n;++i)        {            ans1=(ans1+k)%i;            if(i==2)            {                ans2=1-ans1;                continue;            }            ans2=(ans2+k)%i;            if(i==3)            {                ans3=(0^1^2)^ans1^ans2;                continue;            }            ans3=(ans3+k)%i;        }        printf("%d %d %d\n",ans3+1,ans2+1,ans1+1);    }    return 0;}