链表(单双) 栈 队列 先放一边

单调栈
与双指针类似 通过利用某些性质 达到压缩时间的目的

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

int main()
{
    int n; cin >> n;
    stack<int> s;
    while(n -- )
    {
        int t; cin >> t;

        while(s.size() && s.top() >= t) s.pop();

        if(s.size()) cout << s.top() << ' ';
        else cout << -1 << ' ';

        s.push(t);
    }
    return 0;
}

单调队列
类似单调栈 另:Y总的数组模拟队列是双端的 比STL快

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f;

struct Node
{
    int x, y;
};

int main()
{
    int n, m; cin >> n >> m;
    if(m > n) m = n;

    int mx = -INF;
    int mi = INF;

    vector<int> a(n + 10);
    deque<Node> q;

    for(int i = 1; i <= n; i ++ )
    {
        int t; cin >> t; a[i] = t;

        while(q.size() && q.back().x >= t) q.pop_back();
        while(q.size() && q.front().y <= i - m) q.pop_front();

        if(i - m >= 0)
        {
            if(q.size()) cout << q.front().x << ' ';
            else cout << t << ' ';
        }

        q.push_back({t, i});
    }
    cout << endl;

    deque<Node> qq;
    for(int i = 1; i <= n; i ++ )
    {
        int t; t = a[i];

        while(qq.size() && qq.back().x <= t) qq.pop_back();
        while(qq.size() && qq.front().y <= i - m) qq.pop_front();

        if(i - m >= 0)
        {
            if(qq.size()) cout << qq.front().x << ' ';
            else cout << t << ' ';
        }

        qq.push_back({t, i});
    }
    cout << endl;

    return 0;
}

KMP
和字符串哈希各有千秋的字符串匹配
先一层循环得到next数组 再一层循环得答案

#include <iostream>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;

int n, m;
int ne[N];
char a[N], b[M];

int main()
{
    cin>>n>>a + 1>>m >> b + 1;
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && a[i] != a[j + 1]) j = ne[j];
        if(a[i] == a[j + 1]) j++;
        ne[i] = j;
    }
    for(int i = 1, j = 0; i <= m; i++)
    {
        while(j && b[i] != a[j + 1]) j = ne[j];
        if(b[i] == a[j + 1]) j++;
        if(j == n)
        {
            cout<<i - j<<' ';
            j = ne[j];
        }
    }
    return 0;
}

Trie树 快速存储字符串集合
先来个手写的板子

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

char s[N];
int son[N][26], cnt[N], idx;

void Insert(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
    return ;
}

int Query(char str[])
{
    int p = 0;
    for(int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

int main()
{
    int n; cin >> n;
    while(n -- )
    {
        char op[5]; cin >> op >> s;
        if(op[0] == 'I') Insert(s);
        else cout << Query(s) << endl;
    }
    return 0;
}

来个Trie的应用

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = N * 32;

int idx, a[N], son[M][2];

void Insert(int x)
{
    int p = 0;
    for(int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    return ;
}

int Query(int x)
{
    int p = 0;
    int res = 0;
    for(int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;
        if(son[p][!u])
        {
            res = res * 2 + !u;
            p = son[p][!u];
        }
        else
        {
            res = res * 2 + u;
            p = son[p][u];
        }
    }
    return res;
}

int main()
{
    int ans = 0;
    int n; cin >> n;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        Insert(a[i]);
        ans = max(ans, a[i] ^ Query(a[i]));
    }
    cout << ans << endl;
    return 0;
}

普通并查集 和 带连通块点的并查集 都巨简单
这里记一下食物链的两种解法
首先是Y总版本

#include <bits/stdc++.h>

using namespace std;

const int N = 50000 + 10;

int n, m, f[N], d[N];

int find(int x)
{
    if(f[x] != x)
    {
        int u = find(f[x]);
        d[x] += d[f[x]];
        f[x] = u;
        // 这里的f[x]其实是当前点的祖宗
        // 所以d[x]是当前点到它祖宗节点的距离
        // 所以d[f[x]]表示的是 x之前的祖宗节点 到它现在的祖宗节点的距离
    }
    return f[x];
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n ; i ++ ) f[i] = i, d[i] = 0;

    int ans = 0;
    while(m -- )
    {
        int o, x, y; cin >> o >> x >> y;
        if(x > n || y > n || (o == 2 && x == y)) ans ++ ;
        else
        {
            int xx = find(x);
            int yy = find(y);
            int t = d[y] - d[x];

            if(o == 1)
            {
                if(xx == yy)
                {
                    if(t % 3) ans ++ ;
                }
                else
                {
                    f[xx] = yy;
                    d[xx] += t;
                }
            }
            else
            {
                if(xx == yy)
                {
                    if((t - 1) % 3) ans ++ ;
                }
                else
                {
                    f[xx] = yy;
                    d[xx] += (t - 1);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

然后是扩展域并查集

#include <bits/stdc++.h>

using namespace std;

const int N = 50000 + 10;
const int M = N * 3;

int n, m, f[M];

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

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n * 3; i ++ ) f[i] = i;
    int ans = 0;
    while(m -- )
    {
        int o, x, y; cin >> o >> x >> y;
        if(x > n || y > n || (o == 2 && x == y)) ans ++ ;
        else
        {
            // x_eat x吃的物种
            // x_enemy 吃x的物种
            int x_eat = x + n;
            int x_enemy = x + 2 * n;

            int y_eat = y + n;
            int y_enemy = y + 2 * n;

            if(o == 1)
            {
                if(find(x_eat) == find(y) || find(x_enemy) == find(y)) ans ++ ;
                else
                {
                    f[find(x)] = find(y);
                    f[find(x_eat)] = find(y_eat);
                    f[find(x_enemy)] = find(y_enemy);
                }
            }
            else
            {
                if(find(x) == find(y) || find(x_enemy) == find(y)) ans ++ ;
                else
                {
                    f[find(x_eat)] = find(y);
                    f[find(y_enemy)] = find(x);
                    f[find(x_enemy)] = find(y_eat);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

补充一题（暂时还没有搞懂）
https://codeforces.com/contest/1594/problem/D

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
const int M = N * 2;

int n, m, f[M], s[M];

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while(T -- )
    {
        cin >> n >> m;
        for(int i = 1; i <= n * 2; i ++ ) f[i] = i, s[i] = 0;

        bool flag = 1;
        while(m -- )
        {
            int x, y; cin >> x >> y;
            string o; cin >> o;

            int xx = x + n;
            int yy = y + n;

            if(o == "crewmate")
            {
                if(find(x) == find(yy) || find(y) == find(xx)) flag = 0;
                else
                {
                    f[find(x)] = find(y);
                    f[find(xx)] = find(yy);
                }
            }
            else
            {
                if(find(x) == find(y) || find(xx) == find(yy)) flag = 0;
                else
                {
                    /*
                    为什么都是认祖宗
                    f[find(xx)] = find(y);
                    f[find(yy)] = find(x);
                    就不行？
                    */
                    f[find(y)] = find(xx);
                    f[find(yy)] = find(x);
                }
            }
        }

        if(!flag) cout << -1 << endl;
        else
        {
            // 这整一个else里面的东西都没怎么懂

            for(int i = 1; i <= n; i ++ ) s[find(i)] ++ ;

            int ans = 0;
            for(int i = 1; i <= n; i ++ )
            {
                if(i != find(i)) continue;
                ans += max(s[find(i)], s[find(i + n)]);
            }
            cout << ans << endl;
        }
    }

    return 0;
}

哈希表
开放寻址法

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 100003;

int a[N];

int Find(int x)
{
    int t = (x % M + M) % M;
    while(a[t] != 0x3f3f3f3f)
    {
        t ++ ;
        if(t >= M) t %= M;
    }
    return t;
}

bool Query(int x)
{
    int t = (x % M + M) % M;
    while(a[t] != x && a[t] != 0x3f3f3f3f)
    {
        t ++ ;
        if(t >= M) t %= M;
    }
    if(a[t] == 0x3f3f3f3f) return 0;
    return 1;
}

int main()
{
    memset(a, 0x3f, sizeof a);

    int n; cin >> n;
    while(n -- )
    {
        string x; int y;
        cin >> x >> y;

        // cout << t << endl;

        if(x == "I")
        {
            int t = Find(y);
            a[t] = y;
        }
        else
        {
            if(Query(y)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }

    // for(int i = 1; i <= M; i ++ ) cout << a[i] << ' ';

    return 0;
}

拉链法

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 100003;

int idx;
int h[N], e[N], ne[N];

void Insert(int x)
{
    int k = (x % M + M) % M;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx; idx ++ ;
    return ;
}

bool Find(int x)
{
    int t = (x % M + M) % M;
    for(int i = h[t]; i != -1; i = ne[i])
    {
        if(e[i] == x) return 1;
    }
    return 0;
}

int main()
{
    memset(h, -1, sizeof h);

    int n; cin >> n;
    while(n -- )
    {
        string x; int y;
        cin >> x >> y;

        if(x == "I")
        {
            Insert(y);
        }
        else
        {
            if(Find(y)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }

    return 0;
}

字符串哈希

#include <bits/stdc++.h>

using namespace std;

#define int unsigned long long

const int N = 1e5 + 10;
const int M = 131;

int n, m;
int a[N], b[N];
char c[N];

int32_t main()
{
    a[0] = 0; b[0] = 1;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
    {
        cin >> c[i];
        a[i] = a[i - 1] * M + c[i];
        b[i] = b[i - 1] * M;
    }

    while(m -- )
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        // int x = a[r1] % b[r1 - l1];
        // int y = a[r2] % b[r1 - l1];

        // Hack样例
        // 10 3
        // Ac1Ac1Ac1A
        // 1 6 4 9
        // 1 5 3 7
        // 2 3 5 6

        // 因为你用 ULL模2的64次方 只能保证模后+—*/结果相同
        // 并不能保证末位取模后还是你想要的
        // 所以 老实用Y总方法
        // h[r] - h[l - 1] * p[r - l + 1];
        int x = a[r1] - a[l1 - 1] * b[r1 - l1 + 1];
        int y = a[r2] - a[l2 - 1] * b[r2 - l2 + 1];

        // cout << x << ' ' << y << endl;

        if(x == y) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}