鄙人不才，此中鄙陋甚多，望海涵！！！
这里我们来详细讲解一下圆桌问题的相关题目
第一道一定是hdu的4841了,罪恶的源头
圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。
输入：多组数据，每组数据输入：好人和坏人的人数n（<=32767）、步长m（<=32767）；
输出：对于每一组数据，输出2n个大写字母，‘G’表示好人，‘B’表示坏人，50个字母为一行，不允许出现空白字符。相邻数据间留有一空行。
输入
2 3
2 4
输出
GBBG
BGGB
C++代码
#include<iostream>
#include<vector>
using namespace std;
vector<int> res;
int main()
{
int n,m;
while(cin>>n>>m)
{
res.clear();//用res来模拟圆桌
for(int i=0;i<2*n;i++) res.push_back(i);//先将这2n个人放入res中；
int p=0;
for(int i=0;i<n;i++)//一共需要杀死n个坏人
{
p=(p+m-1)%res.size();//每次先定位该死的坏人的位置，注意res下标从0开始，而且
//涉及到取余问题，记得减一
res.erase(res.begin()+p);//将坏人抹杀
}
for(int i=0,cnt=0;i<2*n;i++)
{
if(i%50==0 && i) puts("");//每50行输出一个换行
if(cnt<res.size() && res[cnt]==i)//留下的人都是好人，只有好人才会i==res[cnt]
{//别忘了cnt<res.size()这个限制条件，不然会wa，可能因为随机值的原因吧！
printf("G");
cnt++;
}
else printf("B");
}
cout<<endl<<endl;
}
return 0;
}
圆桌问题的简单应用
题目
“Eeny meeny miny moe” is a well-known nursery rhyme inEnglish, used (among other things) by kids to “randomly”select members of a team. It exists in many variations, oneof which goes like this:
Eeny, meeny, miny, moe,
Catch a tiger by the toe.
If he hollers, let him go,
Eeny, meeny, miny, moe.
Similar verses exist in most languages, such as “Ulle dulle dof” in Finnish, “Akka bakka bonka rakka” in Norwegian, and “Ole dole doff” in Swedish.
Two teams are to be selected for a game and the rhyme is used to select one kid for a team at a time, alternating between the two teams, until all kids have been selected. The kids are standing in a circle. In each selection round we start counting the kids in clockwise order around the circle, skipping one kid for every word in the rhyme, until the last word. The kid matching the last word is chosen for the current team and then the next round starts. In all rounds but the first, the counting starts at the next remaining kid (in clockwise order) after the one that was selected in the previous round.
Given such a rhyme, and a group of kids, can you tell which kids will be in which team?
Illustration of the first three rounds of Sample Input 1. In rounds 1 and 3, Alvar and Rakel get selected for the first team, and in round 2, Lisa is selected for the second team. In round 4 (not shown), only Kalle remains and is selected for the second team.
Input
The first line of input contains the rhyme, consisting of a list of words separated by spaces. The second line of input contains an integer n (1 ≤ n ≤ 100), the number of kids. Then follow the names of the kids, one per line. The kids are given in clockwise order and the first kid listed is the one at which counting starts in the first round.
All words and names consist only of upper and lower case letters ‘A’-‘Z’ and ‘a’-‘z’. No input line is empty or longer than 100 characters (excluding the newline character at the end of the line).
Output
Output the two teams, starting with the one whose first member is chosen first. For each team, output the number of kids in the team, followed by the names of the kids in the team, in the same order as they were chosen for the team.
样例1输入
eeny meeny miny
4
Kalle
Lisa
Alvar Rakel
样例1输出
2
Alvar
Rakel
2
Lisa
Kalle
样例2输入
Every Other
3
a
b
c
样例2输出
2
b
c
1
a
C++code
#include<iostream>
#include<vector>
using namespace std;
vector<string> a;
vector<string> b;
vector<string> sum;
string s;
int main()
{
int cnt=0,n=0;
while(cin>>s)
{
if(s[0]>='a' && s[0]<='z' || s[0]>='A' && s[0]<='Z') cnt++;
else
{
for(int i=0;i<s.size();i++) n=n*10+s[i]-'0';
break;
}
}
for(int i=0;i<n;i++)
{
string item;
cin>>item;
sum.push_back(item);
}
int m=1;
while(sum.size())
{
int pos=(pos+cnt-1)%sum.size();
if(m&1)
{
a.push_back(sum[pos]);
sum.erase(sum.begin()+pos);
}
else
{
b.push_back(sum[pos]);
sum.erase(sum.begin()+pos);
}
m++;
}
cout<< a.size() <<endl;
for(auto x:a) cout<< x <<endl;
cout<< b.size() <<endl;
for(auto x:b) cout<< x <<endl;
return 0;
}
总算是回到了游戏这题，这题其实就是属于圆桌问题的变种，关键就在于把报数的过程转化为每隔几个人就会被淘汰的问题，这就相当于n个人只有一个是好人，从第一个人开始每隔几个人就会抹杀一个坏人，最终剩下一个好人胜出
关键：处理这个隔几个人的问题
题目请到ccf官网自提
C++ Code
#include<iostream>
#include<vector>
using namespace std;
vector<int> res;//用res来模拟圆桌
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) res.push_back(i);
for(int i=0,cnt=1,m=0;i<n-1;) //需要淘汰n-1个人
{
if(cnt%k==0 || cnt%10==k)
{
int p=(p+m)%res.size();
res.erase(res.begin()+p);
m=0,i++;//将m归0,并且淘汰人数加1
}
else m++;//这里m就是距离上一次淘汰所间隔人数
cnt++;//cnt表示所报的数
}
cout<< res[0] <<endl;
return 0;
}
