http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4443
题解:经典的约瑟夫环问题
参考https://blog.csdn.net/tingyun_say/article/details/52343897
如果不一次处理完,重复操作可能超时
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
using namespace std;
typedef long long ll;
const int N=10000+10;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m;
int a[N];
int yuesefu(int n,int m){
if(n == 1){
return 0; //这里返回下标,从0开始,只有一个元素就是剩余的元素0
}
else{
a[n-1]=yuesefu(n-1,m);
return (a[n-1] + m) % n; //我们传入的n是总共多少个数
}
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d",&t);
a[10000]=yuesefu(10000,233);
while(t--){
scanf("%d",&n);
cout<<a[n]+1<<endl;
}
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
题解:
因为一直k 是233,所有人站成一个环,如果知道了x 个站成一个环的时候,出去人的相对顺序(最后一个出去的人的序列是1,第一个出去的人的编号是x),那么可以通过这个顺序知道x+1 个人占成一个环的时候,出去的相对顺序。即找到编号为x 的人,往前数232 个人和第233 个人之间插入一个位置,这个位置就是编号为x+1 的人。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int main()
{
f[1] = 0;
for(int i = 2; i < N; ++i) f[i] = (f[i - 1] + 233) % i;
int t;
scanf("%d", &t);
while(t--){
int n;
scanf("%d", &n);
printf("%d\n", f[n] + 1);
}
return 0;
}