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 这个类似于约瑟夫环，只是第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;
}