2020牛客国庆集训派对day2 A
AKU NEGARAKU
https://ac.nowcoder.com/acm/contest/7818/A
题意
给你 两个整数，要求求出约瑟夫问题中最后一个人是谁。
分析
总所周知，约瑟夫问题有模拟 ，线性
。这里解释一种
的解决方法。考虑到我们每次走
个删一个，那么在一圈以内我们可以删掉
个。我们可以模拟这个过程递归求解。由于每次递归问题规模变为
。通过归纳验证时间复杂度大概是
代码
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return f?-x:x;
}
int solve(int n,int k) {
if(n==1)return 0;
if(k==1)return n-1;
if(k>n)return (solve(n-1,k)+k)%n;
int res=solve(n-n/k,k);
res -= n%k;
if(res<0)res+=n;
else res+=res/(k-1);
return res;
}
int main() {
while(1) {
int n=read(),k=read();
if(!n&&!k) return 0;
printf("%d\n",solve(n,k)+1);
}
}比赛题解 文章被收录于专栏
近期比赛的题解应该有吧。。。
