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");
}
}
05-01 03:50