发表更新基础 / 模板6 分钟读完 (大约826个字)

数据结构

本文内容参考 OI Wiki。

并查集

例题

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class UnionFind {
    private final int[] f, s;
    private int c;

    public UnionFind(int n) {
        c = n;
        f = new int[n];
        s = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
            s[i] = 1;
        }
    }

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

    public void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        f[ry] = rx;
        s[rx] += s[ry];
        c--;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int size(int x) {
        return s[find(x)];
    }

    public int count() {
        return c;
    }
}

树状数组

例题

实现

单点修改，区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class BIT {
    private final int n;
    private final long[] t;

    public BIT(int n) {
        this.n = n;
        t = new long[n + 1];
    }

    public void add(int i, int k) {
        for (; i <= n; i += i & -i) {
            t[i] += k;
        }
    }

    public long sum(int x) {
        long res = 0;
        for (; x > 0; x &= x - 1) {
            res += t[x];
        }
        return res;
    }

    public long get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

区间修改，单点查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class BIT {
    private final int n;
    private final long[] t;

    public BIT(int n) {
        this.n = n;
        t = new long[n + 1];
    }

    private void add(int i, int k) {
        for (; i <= n; i += i & -i) {
            t[i] += k;
        }
    }

    public void add(int l, int r, int k) {
        add(l, k);
        add(r + 1, -k);
    }

    public long sum(int x) {
        long res = 0L;
        for (int i = x; i > 0; i &= i - 1) {
            res += t[i];
        }
        return res;
    }

    public long get(int x) {
        return sum(x);
    }
}

区间修改，区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class BIT {
    private final int n;
    private final long[] t1, t2;

    public BIT(int n) {
        this.n = n;
        t1 = new long[n + 1];
        t2 = new long[n + 1];
    }

    private void add(int i, int k) {
        long p = (long) k * i;
        for (; i <= n; i += i & -i) {
            t1[i] += k;
            t2[i] += p;
        }
    }

    public void add(int l, int r, int k) {
        add(l, k);
        add(r + 1, -k);
    }

    public long sum(int x) {
        long s1 = 0, s2 = 0;
        for (int i = x; i > 0; i &= i - 1) {
            s1 += t1[i];
            s2 += t2[i];
        }
        return s1 * (x + 1) - s2;
    }

    public long get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

线段树

例题

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class SegmentTree {
    private final int n;
    private final long[] t, z;

    public SegmentTree(int[] a) {
        n = a.length;
        t = new long[4 * n];
        z = new long[4 * n];
        build(a, 1, 1, n);
    }

    private void build(int[] a, int i, int l, int r) {
        if (l == r) {
            t[i] = a[l - 1];
            return;
        }
        int mid = l + (r - l) / 2;
        build(a, 2 * i, l, mid);
        build(a, 2 * i + 1, mid + 1, r);
        t[i] = t[2 * i] + t[2 * i + 1];
    }

    private void lazy(int i, int lo, int hi, long k) {
        t[i] += k * (hi - lo + 1);
        z[i] += k;
    }

    private void down(int i, int lo, int hi) {
        if (z[i] == 0) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        lazy(2 * i, lo, mid, z[i]);
        lazy(2 * i + 1, mid + 1, hi, z[i]);
        z[i] = 0;
    }

    public void add(int l, int r, int k) {
        if (l > r) return;
        add(1, 1, n, l, r, k);
    }

    private void add(int i, int lo, int hi, int l, int r, int k) {
        if (lo >= l && hi <= r) {
            lazy(i, lo, hi, k);
            return;
        }
        down(i, lo, hi);
        int mid = lo + (hi - lo) / 2;
        if (l <= mid) add(2 * i, lo, mid, l, r, k);
        if (r > mid) add(2 * i + 1, mid + 1, hi, l, r, k);
        t[i] = t[2 * i] + t[2 * i + 1];
    }

    public long get(int l, int r) {
        if (l > r) return 0L;
        return get(1, 1, n, l, r);
    }

    private long get(int i, int lo, int hi, int l, int r) {
        if (lo >= l && hi <= r) {
            return t[i];
        }
        down(i, lo, hi);
        long res = 0L;
        int mid = lo + (hi - lo) / 2;
        if (l <= mid) res += get(2 * i, lo, mid, l, r);
        if (r > mid) res += get(2 * i + 1, mid + 1, hi, l, r);
        return res;
    }
}

稀疏表（Sparse Table）

例题

实现

1
System.out.println("TODO");
发表更新基础 / 模板10 分钟读完 (大约1439个字)

数学

本文内容参考《算法导论》，OI Wiki。（数学好难，暂时搁置）

快速幂

例题

整数

时间复杂度：\(O(\log{n})\)。

1
2
3
4
5
6
7
8
9
10
11
private static final long MOD = 1_000_000_007;

private static long pow(long x, long n) {
    long res = 1L;
    for (; n != 0; x = x * x % MOD, n >>= 1) {
        if ((n & 1) == 1) {
            res = res * x % MOD;
        }
    }
    return res;
}

矩阵

时间复杂度：\(O(\log{n})\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static final int MOD = 1_000_000_007;

private static long[][] pow(long[][] x, long n) {
    long[][] res = {{1, 0}, {0, 1}};
    for (; n != 0; x = mul(x, x), n >>= 1) {
        if ((n & 1) == 1) {
            res = mul(res, x);
        }
    }
    return res;
}

private static long[][] mul(long[][] a, long[][] b) {
    long[][] c = new long[2][2];
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
            }
        }
    }
    return c;
}

数论

例题

判断质数

时间复杂度 \(O(n\sqrt{n})\)。

1
2
3
4
5
6
7
private static boolean isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

质数筛法

埃氏筛

时间复杂度 \(O(n\log{\log{n}})\)，筛掉质数的倍数，每个合数都会被筛它的质因数的个数次。

1
2
3
4
5
6
7
8
9
10
11
12
private static boolean[] sieveOfEratosthenes(int n) {
    boolean[] np = new boolean[n + 1];
    np[0] = np[1] = true;
    
    for (int i = 2; i <= n / i; i++) {
        if (np[i]) continue;
        for (int j = i; j <= n / i; j++) {
            np[j * i] = true;
        }
    }
    return np;
}

欧拉筛

时间复杂度 \(O(n)\)，每个合数都只被它的最小质因数筛掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static boolean[] sieveOfEuler(int n) {
    int cnt = 0;
    int[] p = new int[n + 1];
    boolean[] np = new boolean[n + 1];
    np[0] = np[1] = true;
    
    for (int i = 2; i <= n; i++) {
        if (!np[i]) p[cnt++] = i;
        for (int j = 0; p[j] <= n / i; j++) {
            np[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }
    return np;
}

分解质因数

时间复杂度 \(O(\sqrt{n})\)。

1
2
3
4
5
6
7
8
9
10
11
private static Map<Integer, Integer> primeFactors(int x) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 2; i <= x / i; i++) {
        while (x % i == 0) {
            x /= i;
            map.merge(i, 1, Integer::sum);
        }
    }
    if (x > 1) map.merge(x, 1, Integer::sum);
    return map;
}

欧拉函数

欧拉函数 \(\phi(n)\)，表示 \([1,n]\) 范围内和 \(n\) 互质的数的个数，有如下性质：

  • 若 \(\gcd(a,b)=1\)，则 \(\phi(a\times b)=\phi(a)\times \phi(b)\)。
  • 若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，其中 \(p_{i}\) 为质数，则 \(\phi(n)=n\times\prod_{i=1}^{k}(1-\frac{1}{p_{i}})\)。

我们可以使用分解质因数求解某个数的欧拉函数，时间复杂度为 \(O(\sqrt{n})\)；也可以使用欧拉筛来求解 \([1,n]\) 范围内所有数的欧拉函数，时间复杂度为 \(O(n)\)。在欧拉筛中，每个合数都是被它的最小质因子筛掉，设 \(p\) 是 \(n\) 的最小质因子，则 \(n=n^{\prime}\times p\)，分类讨论：

  • 如果 \(n^{\prime}\bmod p\neq 0\)，因为 \(p\) 是质数，所以 \(\gcd(n^{\prime},p)=1\)，则 \(\phi(n)=\phi(n^{\prime})\times \phi(p)=\phi(n^{\prime})\times (p-1)\)。
  • 如果 \(n^{\prime}\bmod p=0\)，则 \(\phi(n)=p\times n^{\prime}\times\prod_{i=1}^{k}(1-\frac{1}{p_{i}})=p\times \phi(n^{\prime})\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private static int[] sieveOfEuler(int n) {
    int cnt = 0;
    int[] p = new int[n + 1];
    int[] phi = new int[n + 1];
    boolean[] np = new boolean[n + 1];
    phi[1] = 1;
    np[0] = np[1] = true;

    for (int i = 2; i <= n; i++) {
        if (!np[i]) {
            p[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; p[j] <= n / i; j++) {
            np[p[j] * i] = true;
            if (i % p[j] == 0) {
                phi[p[j] * i] = p[j] * phi[i];
                break;
            }
            phi[p[j] * i] = (p[j] - 1) * phi[i];
        }
    }
    return phi;
}

最大公约数

欧几里得算法

时间复杂度 \(O(\log{\max(a,b)})\)。求得最大公约数之后，使用 \(\gcd(a,b)\times\operatorname{lcm}(a,b)=a\times b\) 公式可以得到最小公倍数。

1
2
3
4
private static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

扩展欧几里得算法

常用于求解 \(ax+by=\gcd(a,b)\) 的一组解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private static int x, y;

private static int exgcd(int a, int b) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b);
    int t = x - a / b * y;
    x = y;
    y = t;
    return d;
}

其他知识

约数个数

若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，则 \(d_{n}=\prod_{i=1}^{k}(c_{i}+1)\)。

约数之和

若 \(n=\prod_{i=1}^{k}{p_{i}^{c_{i}}}\)，则 \(s_{n}=\prod_{i=1}^{k}\sum_{j=0}^{c_{i}}{p_{i}^{j}}\)。

裴蜀定理

若 \(a,b\) 是整数，则对于任意的整数 \(x,y\)，\(ax+by\) 总是 \(\gcd(a,b)\) 的倍数，并且存在整数 \(x,y\)，使得 \(ax+by=\gcd(a,b)\)。特别的，若存在整数 \(x,y\) 使得 \(ax+by=1\)，则 \(\gcd(a,b)=1\)，即 \(a,b\) 互质。

费马小定理

若 \(p\) 是质数，\(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv 1\pmod{p}\)。

欧拉定理

若 \(\gcd(a,n)=1\)，则 \(a^{\phi(n)}\equiv 1\pmod{n}\)。

模乘法逆元

若 \(p\) 是质数，根据费马小定理，有 \(a\times a^{-1}\equiv 1\equiv a^{p-1}\pmod{p}\)，得到 \(a^{-1}\equiv a^{p-2}\pmod{p}\)。

若 \(b\) 是任意整数，求 \(a\) 的逆元，等价于求 \(ax\equiv 1\pmod{b}\) 的解，等价于求 \(ax+by=1\) 的解。如果 \(\gcd(a,b)=1\)，则可以使用扩展欧几里得算法求解该方程。如果 \(\gcd(a,b)\neq 1\)，根据裴蜀定理可知方程无解（或者可以将方程变换为 \(\frac{a}{g}x+\frac{b}{g}y=\frac{1}{g}\)，等式左边是整数，右边不是整数，方程无解），即逆元不存在。

线性同余方程

求 \(ax\equiv c\pmod{b}\) 的解，等价于求 \(ax+by=c\) 的解，同样的，当 \(\gcd(a,b)\mid c\) 时方程有解。使用扩展欧几里得算法可以求出 \(ax+by=\gcd(a,b)\) 的解，然后将方程变换为 \(a\frac{c}{\gcd(a,b)}x_{0}+b\frac{c}{\gcd(a,b)}y_{0}=c\)，可以得到方程的解。

发表更新基础 / 模板10 分钟读完 (大约1539个字)

字符串

本文内容参考《算法》，《算法导论》，OI Wiki。

字符串匹配

例题

暴力

  • 时间复杂度：最坏 \(O(NM)\)，平均 \(O(N)\)。
  • 空间复杂度：\(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
private static int bruteForce(String text, String pattern) {
    int i, j;
    int n = text.length(), m = pattern.length();
    for (i = 0, j = 0; i < n && j < m; i++) {
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        } else {
            i -= j;
            j = 0;
        }
    }
    return j == m ? i - m : -1;
}

KMP

  • 时间复杂度：\(O(N)\)。
  • 空间复杂度：\(O(M)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private static int kmp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    if (m > n) return -1;
    
    // 处理模式串
    // next[i] 表示 pattern 的子串 [0, i] 的最长相等前后缀的长度
    int[] next = new int[m];
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        next[i] = j;
    }
    
    // 匹配文本串
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        if (text.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }
    return -1;
}

Boyer-Moore

  • 时间复杂度：最坏 \(O(NM)\)，平均 \(O(\frac{N}{M})\)。
  • 空间复杂度：\(O®\)。
1
System.out.println("TODO");

Rabin-Karp

  • 时间复杂度：\(O(N)\)。
  • 空间复杂度：\(O(1)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
private static final int P = 13331;

// MOD = 2^64
private static int rabinKarp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    if (m > n) return -1;

    long PM = pow(P, m - 1);
    long patHash = hash(pattern, m);
    long txtHash = hash(text, m);
    if (txtHash == patHash) {
        return 0;
    }

    for (int i = m; i < n; i++) {
        txtHash = txtHash - text.charAt(i - m) * PM;
        txtHash = txtHash * P + text.charAt(i);
        if (txtHash == patHash) {
            return i - m + 1;
        }
    }
    return -1;
}

private static long pow(int a, int n) {
    long res = 1L, x = a;
    for (; n != 0; x *= x, n >>= 1) {
        if ((n & 1) == 1) {
            res *= x;
        }
    }
    return res;
}

private static long hash(String s, int m) {
    long h = 0L;
    for (int i = 0; i < m; i++) {
        h = h * P + s.charAt(i);
    }
    return h;
}

字符串哈希

例题

  • E. Compress Words（这题使用 \(MOD=2^{64}\) 一直在第 65 个测试点 WA，看来还是模质数比较好）。

实现

  • 时间复杂度：预处理 \(O(N)\)，获取哈希值 \(O(1)\)。
  • 空间复杂度：\(O(N)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class StringHash {
    private final int K = 2;
    private static final long[] b = {131, 13331};
    private static final long[] m = {1_000_000_007, 998244353};

    private int index;
    private final long[][] h, p;

    public StringHash(int n) {
        h = new long[K][n + 1];
        p = new long[K][n + 1];
        for (int i = 0; i < K; i++) {
            p[i][0] = 1;
        }
    }

    public StringHash(char[] s) {
        this(s.length);
        for (char c : s) add(c);
    }

    public void add(char c) {
        for (int j = 0; j < K; j++) {
            p[j][index + 1] = p[j][index] * b[j] % m[j];
            h[j][index + 1] = (h[j][index] * b[j] + c) % m[j];
        }
        index++;
    }

    public long[] get(int l, int r) {
        long[] res = new long[K];
        for (int i = 0; i < K; i++) {
            long t = h[i][r + 1] - h[i][l] * p[i][r - l + 1];
            res[i] = (t % m[i] + m[i]) % m[i];
        }
        return res;
    }

    public int length() {
        return index;
    }
}

字典树（Trie）

例题

实现

  • 时间复杂度：插入和查找都是 \(O(k)\)，其中 \(k\) 为字符串的长度。
  • 空间复杂度：\(O(nR)\)，其中 \(n\) 为节点总数，\(R\) 为字母表大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Trie {
    private static final int R = 26;
    private final Node root;

    private static class Node {
        boolean exist;
        Node[] next = new Node[R];
    }

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.next[idx] == null) {
                node.next[idx] = new Node();
            }
            node = node.next[idx];
        }
        node.exist = true;
    }

    public boolean search(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.next[idx] == null) {
                return false;
            }
            node = node.next[idx];
        }
        return node.exist;
    }
}

AC 自动机

例题

实现

  • 时间复杂度：插入 \(O(k)\)，构建 \(O(nR)\)，查询 \(O(k+n)\)，其中 \(k\) 为字符串的长度。
  • 空间复杂度：\(O(nR)\)，其中 \(n\) 为节点总数，\(R\) 为字母表大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class AhoCorasickAutomaton {
    private static final int R = 26;
    private final Node root;

    // 按插入顺序存储模式串尾字符对应的节点
    private final List<Node> patternNodes;

    // 所有节点按层次遍历顺序存储（代码没有存根节点）
    private final List<Node> levelOrderNodes;

    private static class Node {
        int cnt; // 节点出现在文本串中的次数，懒更新
        Node fail; // 节点的失配指针，指向当前节点的最长后缀节点
        Node[] next = new Node[R];
    }

    public AhoCorasickAutomaton() {
        root = new Node();
        patternNodes = new ArrayList<>();
        levelOrderNodes = new ArrayList<>();
    }

    // 插入模式串
    public void insert(String pattern) {
        Node node = root;
        for (int i = 0; i < pattern.length(); i++) {
            int idx = pattern.charAt(i) - 'a';
            if (node.next[idx] == null) {
                node.next[idx] = new Node();
            }
            node = node.next[idx];
        }
        patternNodes.add(node);
    }

    // 构建失配指针和 Trie 图
    public void build() {
        // 将根节点的直接子节点入队，并构建节点的失配指针和 Trie 图
        // 提前入队是因为根节点和其直接子节点与其他节点的处理逻辑不同
        root.fail = root;
        Queue<Node> q = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            if (root.next[i] == null) {
                root.next[i] = root;
            } else {
                root.next[i].fail = root;
                q.offer(root.next[i]);
            }
        }
        // 层次遍历，构建失配指针和 Trie 图
        while (!q.isEmpty()) {
            Node node = q.poll();
            levelOrderNodes.add(node);
            for (int i = 0; i < R; i++) {
                if (node.next[i] == null) {
                    node.next[i] = node.fail.next[i];
                } else {
                    node.next[i].fail = node.fail.next[i];
                    q.offer(node.next[i]);
                }
            }
        }
    }

    // 查询每个模式串在文本串中的出现次数
    public void query(String text, int[] cnt) {
        // 懒更新出现次数
        Node node = root;
        for (int i = 0; i < text.length(); i++) {
            int idx = text.charAt(i) - 'a';
            node = node.next[idx];
            node.cnt++;
        }
        // 倒序层次遍历，进一步沿着失配指针传递出现次数
        // 倒序遍历是因为失配指针必然在更上层，所以从下向上传递可以保证正确性
        for (int i = levelOrderNodes.size() - 1; i >= 0; i--) {
            node = levelOrderNodes.get(i);
            node.fail.cnt += node.cnt;
        }
        // 获取每个模式串的出现次数
        for (int i = 0; i < patternNodes.size(); i++) {
            cnt[i] += patternNodes.get(i).cnt;
        }
    }
}

正则表达式

例题

实现

  • 时间复杂度：构造 NFA \(O(m)\)，匹配 \(O(nm)\)，其中 \(m\) 为正则表达式的长度，\(n\) 为文本串的长度。
  • 空间复杂度：构造 NFA \(O(m)\)，匹配 \(O(m)\)。
1
System.out.println("TODO");
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×