[原创]HDU 5643 bestcoder Round #75 king's game [威瑟夫问题]
[原创]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,那么这样不断倒推就可以推出其在第一轮的编号,也即他本来的编号。
附本题代码
1 | # include<iostream> |