8
HDU5643 King's Game（约瑟夫环）
source link: https://arminli.com/hdu5643/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU5643 King's Game（约瑟夫环）
March 15, 2016
题意：变形的约瑟夫环，最初为每个人编号 1 到 n，第 i 次删去报号为 i 的人，然后从它的下一个人开始重新从 1 开始报号，问最终剩下第几号人？
和HDU2925相似，同样是从后往前递推，改变下 m 的值即可。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
using namespace std;
int f[5005];
int main(){
//freopen("a.txt", "r", stdin);
int t; cin >> t;
while(t--){
int n;
scanf("%d", &n);
f[1] = 0;
int m = n-1;
for(int i = 2; i <= n; i++){
f[i] = (f[i-1]+m)%i;
m--;
}
cout << f[n]+1 << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK