链接：https://vjudge.net/problem/UVA-1452
思路：约瑟夫环问题的变形，之前一直对约瑟夫环的递推没搞太懂，现在大概看懂了。约瑟夫环是可以分解成子问题，即如果现在有n人，出列一人后就变成n-1人的子问题，同时建立一个映射关系，而求最后一人的则是从1个人推回n人的情况。求最后三人的可以看作先求最后一人，然后把最后一人除去，变成n-1个人求最后一人，然后再除去，变成n-2个人求最后一人。
附上约瑟夫环问题的递推公式：f（n） =（ f（n-1）+k）% n
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include<iostream>
using namespace std;
int t,n,k,ans1,ans2,ans3;
int main(){
cin>>t;
while(t--){
cin>>n>>k;
ans1 = 0;
ans2 = (k-1)%2;
ans3 = (k-1)%3;
for(int i=2;i<=n;i++){
ans1 = (ans1+k)%i;
}
for(int i=3;i<=n;i++){
ans2 = (ans2+k)%i;
}
for(int i=4;i<=n;i++){
ans3 = (ans3+k)%i;
}
cout<<ans3+1<<" "<<ans2+1<<" "<<ans1+1<<endl;
}
return 0;
}
|
近期评论