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

Tabris

CSDNhdubestcoder

发布于：2016年3月13日

次浏览

[原创]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 7| 0 2 3 4 5 6 7|X 2 0 4 5 6 7|X 2 X 4 5 0 7|X 2 X 4 0 X 7|X 0 X 4 X X 7|
|标号|1 2 3 4 5 6 7| 0 1 2 3 4 5 6|X 5 0 1 2 3 4|X 2 X 3 4 0 1|X 2 X 3 X 0 1|X X 0 1 X X 2|
|结果|preson.1 out|person.3 out|person.6 out|person.5 out|person.2 out|person.7 out|
||No.1 out|No.2 out|No.3 out|No.4 out|No.2(5%3) out|No.2(6%2) out|

person.4 is winer

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

附本题代码

# 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;
}