[原创]HDU 5643 bestcoder Round #75 king’s game [威瑟夫问题]

2016-03-13 16:27:26 Tabris_ 阅读数：579

博客爬取于2020-06-14 22:44:50
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50878582

中文题意
题目链接 HDU 5643

King’s Game Accepts: 249 Submissions: 671
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
问题描述
为了铭记历史，国王准备在阅兵的间隙玩约瑟夫游戏。它召来了 n(1\le n\le 5000)n(1≤n≤5000) 个士兵，逆时针围成一个圈，依次标号 1, 2, 3 … n1,2,3…n。

第一轮第一个人从 11 开始报数，报到 11 就停止且报到 11 的这个人出局。

第二轮从上一轮出局的人的下一个人开始从 11 报数，报到 22 就停止且报到 22 的这个人出局。

第三轮从上一轮出局的人的下一个人开始从 11 报数，报到 33 就停止且报到 33 的这个人出局。

第 n - 1n−1 轮从上一轮出局的人的下一个人开始从 11 报数，报到 n - 1n−1 就停止且报到 n - 1n−1 的这个人出局。

最后剩余的人是幸存者，请问这个人的标号是多少？
输入描述
第一行一个整数表示测试组数：T(0 < T≤5000) 。

每组数据占一行，包含一个整数 nn，表示 nn 个人围成一圈。
输出描述
共 TT 行。对每组数据，输出幸存者的编号。
输入样例
2
2
3
输出样例
2
2
Hint
对于第一组数据，一开始报到 11 的人即标号为 11 的人退出，幸存者是 22 号。

对于第二组数据，一开始报到 11 的人即标号 11 的人退出。接着 22 号报 11，33 号报 22，报到 22 的人即 33 号退出。幸存者是 22 号。

**本题是一个威瑟夫问题的变种 **
**跟题目讲述的一样 **
第几轮 报道第几个数的人 就出局
而且每一轮最先报数的是上一轮出局的人的下一个人 （昨天竟然 看成的每轮从标号最小的人开始报数 唉 模拟打表都打错了。。。）
所以要找到剩下的最后一人可以只找出局的人 最后一次出局的人的 下一个人就是最后剩下的人
这样就很好想了
我做个表来模拟下 0表示上一局出局了的人的位置 其他出局用X表示

----第一轮第二轮第三轮第四轮第五轮第六轮
人1 2 3 4 5 6 70 2 3 4 5 6 7X 2 0 4 5 6 7X 2 X 4 5 0 7X 2 X 4 0 X 7X 0 X 4 X X 7
标号1 2 3 4 5 6 70 1 2 3 4 5 6X 5 0 1 2 3 4X 2 X 3 4 0 1X 2 X 3 X 0 1X X 0 1 X X 2
结果preson.1 outperson.3 outperson.6 outperson.5 outperson.2 outperson.7 out
No.1 outNo.2 outNo.3 outNo.4 outNo.2(5%3) outNo.2(6%2) out

person.4 is winer

**设 n为总人数 i为轮数 **
通过上面的表很容易看出
**每一轮重新标号的规律 **
**假设该轮有n个人，那么上一轮(n+1)人，编号为0的人上一轮编号****为k，也即编号为a[n]的人上一轮编号为(a[n]+k)%(n+1)。 **
我们知道最后剩下的人在最后一轮编号肯定为0，那么这样不断倒推就可以推出其在第一轮的编号，也即他本来的编号。

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# include<iostream>
using namespace std;
int a[5005];
int main ()
{
    a[1] = 0;
    int n;
    cin>>n;
    while(n--)
    {
        int k; cin>>k;
        for(int i = 2; i <= n; i++)
        {
            a[i] = (a[i - 1] + k)%i;
        }
    }
    cout<<a[n] + 1<<endl;
}