声明

Sugar_Cube的博客园主页

宇宙安全声明

本文包含了笔者常用的OI算法、数据结构的模板
不保证正确，但能通过相应的模板题（如果有会挂出）
如有错误请在评论区指出（虽然大抵没人看就是了）
码风是笔者的个人习惯（能看懂就好喵），部分代码可能会省略快读Read()
持续更新
咕咕咕

输入输出优化

快读

inline int Read() {
        int res = 0;
        bool flag = false;
        int c = getchar();
        //~c防止EOF读到-1而卡死循环，一般情况可省略
        while ((c < '0' || c > '9') && ~c) {
            flag |= c == '-';
            c = getchar();
        }
        while (c >= '0' && c <= '9') {
            res = (res << 1) + (res << 3) + (c ^ 48);
            c = getchar();
        }
        return flag ? -res : res;
}

数据结构

图论

树上问题

字符串

KMP

Luogu P3375 【模板】KMP

constexpr int AwA = 1e6 + 10;

int n, m;
char s1[AwA], s2[AwA];
int p[AwA];

inline void Pre() {
    p[1] = 0;
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && s2[j + 1] != s2[i]) j = p[j];
        if (s2[j + 1] == s2[i]) j++;
        p[i] = j;
    }
}

inline void Kmp() {
    for (int i = 1, j = 0; i <= n; i++) {
        while (j && s2[j + 1] != s1[i]) j = p[j];
        if (s2[j + 1] == s1[i]) j++;
        if (j == m) printf("%d\n", i - m + 1), j = p[j];
    }
}

int main() {
    scanf("%s%s", s1 + 1, s2 + 1);
    n = int(strlen(s1 + 1)), m = int(strlen(s2 + 1));

    Pre();
    Kmp();

    for (int i = 1; i <= m; i++) printf("%d ", p[i]);
    putchar('\n');
    return 0;
}

Trie树

Luogu P8306 【模板】字典树

constexpr int AwA = 3e6 + 10;

struct Node {
    int ch[62];
    int cnt;
} tr[AwA];

int tot;
char s[AwA];

inline int CharToInt(char c) {
    if (c <= '9') return c - '0' + 52;
    if (c >= 'a') return c - 'a' + 26;
    return c - 'A';
}

inline int NewNode() {
    tot++;
    memset(tr[tot].ch, 0, sizeof(int) * 62);
    tr[tot].cnt = 0;
    return tot;
}

inline void Insert() {
    int u = 1, len = int(strlen(s + 1));
    for (int i = 1; i <= len; i++) {
        int c = CharToInt(s[i]);
        if (!tr[u].ch[c]) tr[u].ch[c] = NewNode();
        u = tr[u].ch[c];
        tr[u].cnt++;
    }
}

int main() {
    int T = Read();
    while (T--) {
        tot = 0;
        NewNode();

        int n = Read(), m = Read();
        for (int i = 1; i <= n; i++) {
            scanf("%s", s + 1);
            Insert();
        }

        while (m--) {
            scanf("%s", s + 1);
            int u = 1, len = int(strlen(s + 1));
            for (int i = 1; i <= len && u; i++) {
                int c = CharToInt(s[i]);
                u = tr[u].ch[c];
            }
            printf("%d\n", tr[u].cnt);
        }
    }

    return 0;
}

数学

计算几何