1
int stk[N], tt = 0; //tt为栈顶下标，下标1作为栈底
2

3
//插入
4
stk[++tt] = x;
5

6
// 弹出
7
tt--;
8

9
// 判空
10
tt != 0 not empty
11
else empty
12

13
//访问栈顶元素
14
stk[tt]

1
int q[N], hh, tt = -1; // hh为队头，tt为队尾，初始化时队列为空，所以tt=-1
2

3
// 只允许在最后面添加元素，只允许在最前面删除元素。
4

5
// 插入
6
q[++tt] = x;
7

8
// 弹出
9
hh ++;
10

11
// 判空
12
if(tt >= hh) not empty
13
else empty
14

15
//取队头、队尾
16
q[hh]、q[tt]

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 1000010;
5

6
int a[N], q[N]; // q为双端队列，里面存的是下标！
7

8
int main()
9
{
10
    int n, k;
11
    scanf("%d%d", &n, &k);
12
    for (int i = 0; i < n; i++)
13
        scanf("%d", &a[i]);
14

15
    // 找每个窗口的最小值，过程中队列q下标指向的元素严格单增
16
    int hh = 0, tt = -1;
17
    for (int i = 0; i < n; i++)
18
    {
19
        if (hh <= tt && i - k + 1 > q[hh]) // i-k+1为滑动窗口第一个元素的下标！！
20
            hh++; // 队列非空且q[hh]已经出窗口，hh++
21

22
        while (hh <= tt && a[i] <= a[q[tt]])
23
            tt--; // 维护队列单调性，即a[q[hh]]永远在窗口中最小
24

25
        q[++tt] = i; // 把下标入队
26

27
        if (i - k + 1 >= 0) // 窗口的最小下标>=0
28
            printf("%d ", a[q[hh]]); // 当窗口形成时，输出队头
29
    }
30

31
    printf("\n");
32
    memset(q, 0, sizeof(q));
33

34
    // 找每个窗口的最大值，过程中队列q下标指向的元素严格单减
35
    hh = 0, tt = -1;
36
    for (int i = 0; i < n; i++)
37
    {
38
        if (hh <= tt && i - k + 1 > q[hh])
39
            hh++; // 同上
40

41
        while (hh <= tt && a[q[tt]] <= a[i])
42
            tt--; // 维护队列单调性，即a[q[hh]]永远在窗口中最大
43
        q[++tt] = i;
44

45
        if (i >= k - 1)
46
            printf("%d ", a[q[hh]]);
47
    }
48

49
    printf("\n");
50
    return 0;
51
}

1
for (int i = 2, j = 0; i <= n; i++)
2
    {
3
        while (j && p[i] != p[j + 1])
4
            j = ne[j];
5
        if (p[i] == p[j + 1])
6
            j++;
7
        ne[i] = j; // 记录答案
8
    }

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 100010, M = 1000010;
4

5
int n, m;
6
int ne[N];
7
char s[M], p[N];
8

9
int main()
10
{
11
    cin >> n >> p + 1 >> m >> s + 1; // p+1和s+1相当于起始输入位置
12

13
    // 预处理出next数组，注意next[1]一定为0，不需要计算
14
    for (int i = 2, j = 0; i <= n; i++)
15
    {
16
        while (j && p[i] != p[j + 1])
17
            j = ne[j];
18
        if (p[i] == p[j + 1])
19
            j++;
20
        ne[i] = j; // 记录答案
21
    }
22

23
    for (int i = 1, j = 0; i <= m; i++) // 匹配i和j+1
24
    {
25
        while (j && s[i] != p[j + 1])
26
            j = ne[j];
27
        // j不断尝试向前走，当匹配不到的时候就“退一步”，相当于跳过了相同的前后缀部分，继续匹配
28
        // 当j退回到最开头，或者匹配成功，跳出while
29
        // 如果j退回到最开头，就去匹配i的下一个位置
30

31
        if (s[i] == p[j + 1])
32
            j++; // 如果本字符匹配成功，j++
33

34
        if (j == n) // S串和P串匹配成功
35
        {
36
            printf("%d ", i - n);
37
            j = ne[j]; // 接着配，准备下一轮i++
38
        }
39
    }
40

41
    return 0;
42
}

1
void insert(char str[]) // 向集合中插入一个字符串
2
{
3
    int p = 0; // root节点
4

5
    for (int i = 0; str[i]; i++)
6
    {
7
        int u = str[i] - 'a'; // 每个字母对应的子节点编号（相当于把a-z映射到0-25）
8

9
        if (!son[p][u]) // p节点没有u这个儿子
10
            son[p][u] = ++idx; // 创建子节点
11

12
        // 此时当前的节点一定存在下一个节点，让p走到下一个点
13
        p = son[p][u];
14
    }
15
    // 出for以后，p 等于字符串 s 的尾字符所对应的 idx
16
    // 此时p已经走完了，所以以p节点为结尾的单词多了一个，把cnt[p] ++
17
    cnt[p]++;
18
}

1
int query(char str[]) // 询问一个字符串在集合中出现了多少次
2
{
3
    int p = 0;
4
    for (int i = 0; str[i]; i++)
5
    {
6
        int u = str[i] - 'a';
7
        if (!son[p][u]) // 找不到str中的某个字符
8
            return 0;
9
        else
10
            p = son[p][u]; // 找到了就往下走一步
11
    }
12
    return cnt[p];
13
}

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 1e5 + 10;
4

5
int son[N][26], cnt[N], idx;
6
char str[N];
7

8
void insert(char str[]) // 向集合中插入一个字符串
9
{
10
    int p = 0; // root节点
11

12
    for (int i = 0; str[i]; i++)
13
    {
14
        int u = str[i] - 'a'; // 每个字母对应的子节点编号（相当于把a-z映射到0-25）
15

16
        if (!son[p][u]) // p节点没有u这个儿子
17
            son[p][u] = ++idx; // 创建子节点
18

19
        // 此时当前的节点一定存在下一个节点，让p走到下一个点
20
        p = son[p][u];
21
    }
22
    // 这个时候，p 等于字符串 s 的尾字符所对应的 idx
23
    // 此时p已经走完了，所以以p节点为结尾的单词多了一个
24
    cnt[p]++;
25
}
26

27
int query(char str[]) // 询问一个字符串在集合中出现了多少次
28
{
29
    int p = 0;
30
    for (int i = 0; str[i]; i++)
31
    {
32
        int u = str[i] - 'a';
33
        if (!son[p][u]) // 找不到str中的某个字符
34
            return 0;
35
        else
36
            p = son[p][u]; // 找到了就往下走一步
37
    }
38
    return cnt[p];
39
}
40
int main()
41
{
42
    int n;
43
    cin >> n;
44
    while (n--)
45
    {
46
        char op[2];
47
        scanf("%s%s", op, str);
48
        if (op[0] == 'I')
49
            insert(str);
50
        else
51
            printf("%d\n", query(str));
52
    }
53
}

1
// Problem: 最大异或对
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/145/
4
/*
5
    把每个数都以二进制存储在Trie树中，
6
    在第一个数字固定的情况下，尽可能地让第二个数的每一位都与第一个数的对应位相反，
7
    这样最终确定的第二个数与第一个数的异或值就最大
8
*/
9
// Powered by CP Editor (https://cpeditor.org)
10
#include <bits/stdc++.h>
11
using namespace std;
12
const int N = 1e5 + 10;
13

14
int n, a[N], son[31 * N][2], idx;
15

16
void insert(int x)
17
{
18
    int p = 0;
19
    for (int i = 30; i >= 0; i--)
20
    {
21
        int u = x >> i & 1; // 从最高位开始获取u的每一位二进制数
22

23
        if (!son[p][u]) // 存入树中
24
            son[p][u] = ++idx;
25
        p = son[p][u];
26
    }
27
}
28

29
int query(int x)
30
{
31
    int p = 0, res = 0;
32
    for (int i = 30; i >= 0; i--)
33
    {
34
        int u = x >> 1 & 1;
35

36
        if (son[p][!u]) // 每次尽可能走到与当前位的值相反的结点
37
        {
38
            p = son[p][!u];
39
            res = res * 2 + !u; // 边走边计算res，多了一个二进制位，相当于给前面的结果*2，再加上2的0次方乘以多的那个0/1
40
        }
41
        else
42
        {
43
            p = son[p][u];
44
            res = res * 2 + u;
45
        }
46
    }
47
    return res; // res存储的是路径上所表示的数
48
}
49
int main()
50
{
51
    int res = 0;
52
    cin >> n;
53
    for (int i = 0; i < n; i++)
54
        cin >> a[i];
55

56
    for (int i = 0; i < n; i++)
57
    {
58
        insert(a[i]); // 先插入再查询，不用特判空集
59
        int t = query(a[i]);
60
        res = max(res, a[i] ^ t); // 异或
61
    }
62
    cout << res << endl;
63
    return 0;
64
}

1
int find(int x)
2
{
3
    if (p[x] != x) // 若x不是根节点
4
        p[x] = find(p[x]); // 路径压缩。此处是递归调用，所以不需要写while
5
    return p[x]; // 返回x的祖宗节点
6
}

1
int find(int m) // 返回一个位置
2
{
3
    int k = (m % N + N) % N;
4

5
    while (h[k] != null && h[k] != m)
6
    {
7
        k++;
8
        if (k == N) // 如果检查完了最后一个数，就要循环去看第一个
9
            k = 0;
10
    }
11
    return k;
12
}
13

14
如果m不在哈希表中，则find()会返回它应该被存储的位置（存储之前，这个位置上的值是null）。
15
如果m在哈希表中，则find()会返回它在的位置。