hdu 5643 BestCoder Round #75

时间:2024-07-06 16:04:26

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\le5000)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 号。

hdu 5643 BestCoder Round #75

/*
hdu 5643 BestCoder Round #75 这个类似于约瑟夫环,只是第i次报i的人被干掉
简单粗暴点就是打表,另外一种就是递推 我们要求的是n个人时最后存活的是谁f[n]
但是我们发现杀掉一个人之后从它的下一位开始重新编号
就成了求f[n-1]的解,所以考虑递推
i+1 i i-1
0 1 2 3 4 5 6 7 -> 1 2 3 4 5 6 7 -> 1 3 4 5 6 7
0 1 2 3 4 5 6 5 0 1 2 3 4
对于第i次而言,我们要干掉第n-i+1个人,而且会从下一位重新编号
所以i->i+1时 每个数的编号相对增加了n-i+1 然后进行取模即可
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define lson (i<<1)
#define rson ((i<<1)|1)
const int maxn = 5005;
int dp[maxn];
int main()
{
int T,m,n;
scanf("%d",&T);
while(T--)
{
dp[1] = 0;
scanf("%d",&n);
for(int i = 2; i <= n; i++)
{
dp[i] = (dp[i-1]+n-i+1)%i;
}
dp[n] += 1;
printf("%d\n",dp[n]);
}
return 0;
}