UVALive 3882 - And Then There Was One【约瑟夫问题】

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1883

题意：n个人围成一圈，第一次删第m个人，然后每数K个删一个人，求最后一个人的编号

分析：典型的约瑟夫问题，和杀人游戏差不多，杀人游戏描述如下:

推导过程：

首先，我们要对问题描述改一下，n个人编号为0,1,2,….,n-1,f[n]表示n个人组成的约瑟夫环按照规则后最后一个存活的编号。

这样之后，首先，我们知道，第一个出列的人的编号(m-1)%n，则我们可以从这个人的后面编号设为k= m % n，则这n-1个人的编号依次为k,k+1,….n-1,n,1,2,…k-2; 则重新编号为0,1,2….n-2,那么我们就可以看作是在这n-1规模的子问题的约瑟夫环的基础上，求解n规模的约瑟夫环。

设n-1规模的子问题的约瑟夫环的解为f[n-1],则n规模约瑟夫环是f[n] = (f[n-1] + k) % n; 证明过程如下： 原来编号依次为k,k+1,….n-1,n,1,2,…k-2; 重新编号以后依次为0,1,2,….,n-2;

f[n] = (f[n-1] + k) % n;(加上k是因为编号要变成n规模里面的编号,不太明白的请看上面的序列) 而 k = m % n; 则f[n] = (f[n-1] + m) % n;递推公式是f[i] = (f[i-1] + k) % i; 而f[1] = 0,则最后的结果是f[n]+1(因为f[n]是0,1…n-1编号的，所以要加1)这样，光秃秃的约瑟夫环问题就结束了。。。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=1111111;
 5 ll dp[N]={0};
 6 int main()
 7 {
 8     ll n,k,m;
 9     while(scanf("%lld%lld%lld",&n,&k,&m)!=EOF)
10     {
11         if(n==0||k==0||m==0)
12             break;
13         for(int i=2;i<n;i++)
14             dp[i]=(dp[i-1]+k)%i;
15         dp[n]=(dp[n-1]+m)%n;
16         printf("%lld\n",dp[n]+1);
17     }
18 }

第一次:        0.1.2 ..... k-1.k.k+1........n-1

去掉k - 1     0.1.2 .....       k.k+1........n-1

从k开始       k.k+1...... n-1.0.1........ k-2

转换           0.1..........n-2  (转换公式: ( i - k + n ) % n )

第二次        0.1..........n-2

去掉k - 1     0.1.2 .....       k.k+1........n-2

从k开始       k.k+1...... n-2.0.1........ k-2

转换           0.1..........n-3  (转换公式: ( i - k + n - 1 ) % ( n - 1 ) )

........

第n次         0

反向递推

a = 0

第n次的0等价于第n-1次。最后一个删除的数  a = ( a + k  ) % 2

a 等价于第n - 2次。最后一个删除的数         a = ( a + k ) % 3

......

a = ( a + k ) % n

那么递推公式出来了

a = 0;
for( int i = 2; i <= n; i ++ ) a = ( a + k ) % i;

再根据m - 1 与 k - 1 的相对位置判断即可

最后需要 + 1

在这题中，m是开始第一个跳出的人，我们并不需要在一开始的时候从m开始， 我们依然从 0 开始，只是最后的结果偏移一下就可以，具体偏移多少，慢慢道来首先，我要强调一点，推导都是从0开始的，这一点请大家牢记心中，而约瑟夫环 的问题特征则是，从不同的位置算起，出列的依次顺序比从0开始的顺序依次顺序 整体向右平移了几个单位。 n=8,k=5,m=3为例,出列依次为3,8,6,5,7,2,4,1 n=8,k=5,m=1为例,出列依次为5,2,8,7,1,4,6,3 整体向右偏移了2,(对n取膜的情况下)

那么，我们只要确定起点就可以了，因为编号是0,1,2,…n-1，而我们是从m(m是1到n)开始算，则起点的偏移就是m-1，而第一个m-1是出队的 我们算的是0开始数k个才是第一个出队的，所以，必须再减掉k-1个偏移(相当于算m-1是第一个出列的，算起点就是减掉k-1个,起点也算一个哟)，这样最后的起点 的偏移就可以算出来了0 + m - 1 - ( k - 1 ) = m - k; 因为偏移量是相同的，那么终点也是这么多则结果为f[n] + m - k 是最终的结果 而这个最终的编号是0,1,2…n-1(n-1编号之内)。最后的结果在加上一个1， 最后结果f[n] + m - k + 1,最后对n取膜，保障在1到n编号就可以了。。。

下面给出AC代码：