当前位置: 代码迷 >> 综合 >> LA 3882 And Then There Was One 约瑟夫变形 *
  详细解决方案

LA 3882 And Then There Was One 约瑟夫变形 *

热度:71   发布时间:2023-09-23 05:31:10.0

 题目地址:http://vjudge.net/problem/UVALive-3882

先想想经典的约瑟夫,不去理m:

题目就是求f[n],即n个人中最后剩的人的标号是f[n](最初的编号)

为了方便,下标从0开始,

正常的思路就是 0~n个人,删去第k个,在0~n-1个人,删去第k个,即每次将第k个人移出队列中,然后再重新编号

因为这样意味着每次去掉下标为k-1的后要以k个为第一个,重新编号,所以要知道重新编号前,重新编号后,这两者编号有什么关系

设y=k;

y -> 0

y+1 ->1

y+2 ->2

...

...

y-2 -> n-2

即f[n-1]+y->f[n]

可以看出:n-1个人的位置映射到n个人的位置就是(x+k)%n

所以,有:

f [1]=0;

f [n] =(f [n-1]+k) %n;  (f[n]一直保存一开始元素的编号,而不是改变编号后的编号)


再会过来看看怎么处理m:

在最后一步时,f[n]=(f[n-1]+m)%n 就好了

因为下标从零开始,所以ans+1;


#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=10000+3;
int f[maxn];
int main(int argc, char const *argv[])
{int n,k,m;while(scanf("%d%d%d",&n,&k,&m)==3&&(n+k+m)){f[1]=0;REP(i,2,n-1) f[i]=(f[i-1]+k)%i;f[n]=(f[n-1]+m)%n+1;printf("%d\n", f[n]);}return 0;
}