https://www.luogu.org/problemnew/show/P1996
约瑟夫环这个问题一直以来都是用循环链表写的，今天才知道有循环队列的写法。以下是要点：
1.循环队列实现环的思想，其实就是队首元素出队，如果它不是该出队的元素，那么就把它继续push进queue，这样就构成了一个环的结构。
2.用一个辅助变量来记录每次要进行的操作，比如每三个人出来选出一个人，temp设置为2，先连续两次出队再入队，此时队首就是该出队的那个元素，把它直接pop扔掉即可。循环执行，直至所有元素出队，打印结果。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
scanf("%d %d", &n, &m);
queue<int>Q;
int i;
for (i = ; i <= n; i++)
{
Q.push(i);
}
int temp;
int a;
while (!Q.empty())
{
temp = m-;
while (temp)
{
a = Q.front();
Q.pop();
Q.push(a);
temp--;
}
a = Q.front();
Q.pop();
printf("%d ", a);
}
}
下面再说一下常规的循环链表写法：
1.这个循环链表一定要是双向的链表有prior和next两个指针，如果只有一个指针，删除中间结点的操作无法完成。
2.计数的时候就用简单粗暴的temp辅助变量来完成计数，用cnt从0加到n再置0那种方法容易出错。
#include <bits/stdc++.h>
using namespace std;
typedef struct LNode
{
int data;
struct LNode*prior;
struct LNode*next;
}LNode;
void creat(LNode*&L, int n)
{
LNode*r;
r = L;
LNode*s;
int i;
r->data = ;
for (i = ; i <= n; i++)
{
s = (LNode*)malloc(sizeof(LNode));
s->data = i;
r->next = s;
s->prior = r;
r = r->next;
}
r->next = L;
L->prior = r;
}
void delete1(LNode*&L, int m,int n)
{
int cnt=;
LNode*r;
LNode*s;
r = L;
int temp;
while (n)
{
temp = m-;
while (temp)
{
r = r->next;
temp--;
}
s = r;
printf("%d ", s->data);
r->prior->next = r->next;
r->next->prior = r->prior;
r = r->next;
free(s);
n--;
} }
int main()
{
int n, m;
scanf("%d %d", &n, &m);
LNode *L;
L = (LNode*)malloc(sizeof(LNode));
creat(L, n);
delete1(L,m,n);
}
http://acm.xidian.edu.cn/problem.php?id=1311
下面这道xdoj1311这道题很有意思，仔细想想和约瑟夫队列很相似。
1.第一点就是要想到的是用队列实现环状结构。
2.奇数回合抽出所有2的倍数的编号，偶数回合抽出所有3的倍数的编号。这个实现其实很简单，偶数就是1234每隔两张抽出1张牌，其实就是temp=1进行一次队首移动到队尾的操作，然后现在队首的元素就是该抽出的元素。3同理，移动队首元素两次即可。
3.与约瑟夫环不同的是约瑟夫环是一个循环走到黑直至队空，而这个是很多回合每个回合都要把所有的牌搞一遍，仔细想想就会发现设置t也就是回合次数，可以完成所有牌的遍历，但有一点非常容易错的地方在于，执行完t次操作之后，你的队首元素不再是1（1既不是2的倍数也不是3的倍数始终未被抽出）。要实现队首元素为1就可以等效为每次都是从1开始的，与一条线性的队列没差别了。这里巧妙的用一个while的循环来保证每次队首的元素都是1.这样问题就解决了。
4.最后要实现队列剩余元素的顺序打印就十分简单了，全放在vector中，然后sort排序，输出即可。
整道题目像是一个加强版的约瑟夫，有些细节还是需要注意的。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d", &T);
int n;
queue<int>Q;
while (T--)
{
int cnt = ;
scanf("%d", &n);
int i;
int m;
for (i = ; i <= n; i++)
{
Q.push(i);
}
int temp;
int t;
while (Q.size() > )
{
if (cnt % != )
{
t = Q.size() / ;
while (t--)
{
temp = ;
while (temp--)
{
m = Q.front();
Q.pop();
Q.push(m);
}
Q.pop();
}
while (Q.front() != )
{
m = Q.front();
Q.pop();
Q.push(m);
}
}
else
{
t = Q.size() / ;
while (t--)
{
temp = ;
while (temp--)
{
m = Q.front();
Q.pop();
Q.push(m);
}
Q.pop();
}
while (Q.front() != )
{
m = Q.front();
Q.pop();
Q.push(m);
}
}
cnt++;
}
vector<int>v;
while (!Q.empty())
{
v.push_back(Q.front());
Q.pop();
}
sort(v.begin(), v.end());
for (i = ; i < v.size(); i++)
{
if (i != v.size() - )
printf("%d ", v[i]);
else
printf("%d", v[i]);
}
printf("\n");
}
}