queue 函数

---

头文件：#include<queue>

声明队列：queue<类型>变量名 ；

q.push()

q.pop()

q.front()

q.size()

q.empty()

重点：% ===> &

约瑟夫问题：P1996 约瑟夫问题AC

思路：

用队列保存每个人的编号，之后根据条件模拟即可

image.png

---

stack函数

头文件：#include<stdck>

建立一个栈 stack<类型>s

加入一个新的元素 s.push(a)

询问栈顶元素 s.top()

弹出栈顶元素 s.pop()

站里面有多少个元素 s.size()

P1739 表达式括号匹配 4个点RE

---

vestor函数

头文件:#include<vector>

建立一个vector<类型名>v ;

加入一个新元素v.push_back(x)

询问第i个元素v[i]

vector里面有多少元素v.size()

清空v.clear()

---

并查集

想了解一下并查集常用的思路和写法：

• 例如：合并集合
• 补集操作
• 如何看出来题是并查集的题，并且如何下手去利用并查集的思路解决问题

P1551 亲戚 AC 看一下并查集的写法

P1197 JSOI2008星球大战 不会

BZOJ2054: 疯狂的馒头
代码：

#include<cstdio>
#include<iostream>
using namespace std;
int father[10000002],a[1000001];

int find(int f)
{
    if (!father[f] || father[f] == f)
      return father[f] = f;
    return father[f] = find( father[f] );
}

int main()
{
    int n , m , p , q , x , y ;
    scanf("%d%d%d%d" , &n , &m , &p , &q) ;
    for (int i = m ; i >= 1 ; i--)
    {
        x=(i * p + q) % n + 1;
        y=(i * q + p) % n + 1;
        if (x > y)
            swap(x , y);
        for (int j = find(x);j <= y;j = find(j))
        {
            a[j] = i;
            father[j] = j + 1;
        }
    }
    for (int i = 1;i <= n;i++)
      printf("%d\n", a[i]);
    return 0;
}

P1525 关押罪犯