题目链接：http://poj.org/problem?id=1012
经典的约瑟夫问题的变形，什么？约瑟夫问题是什么？来，哥给你个传送门
解释下题意，有k个好人和k个换人依次围成一个环，从第一个人开始数，数到m杀掉这个人，问m为多少，使坏人都在好人前面死
由于数据量不大，如果你自己已经打好表，那么有种简单的方法，纯粹为了0MSAC，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int Joseph[]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881,1245064};
int k;
while(cin>>k&&k;)
cout<<Joseph[k]<<endl;
}
|
1
2
3
4
| p[i]=(p[i-1]+m-1)%(n-i+1);
|
由于oj系统反复利用这15组数据解题，打表，以避免超时
完整代码如下
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
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int joseph[14]={0},p[29];
int k,n,m,i;
while(cin>>k&&k;)
{
if(joseph[k])
{
cout<<joseph[k]<<endl;
continue;
}
n=2*k;
m=1;
memset(p,0,sizeof(p));
for(i=1;i<=k;i++)
{
p[i]=(p[i-1]+m-1)%(n-i+1);
if(p[i]<k)
{
i=0;
m++;
}
}
joseph[k]=m;
cout<<joseph[k]<<endl;
}
}
|