发表更新算法 / AtCoder3 分钟读完 (大约461个字)

AtCoder Beginner Contest 326

2UP3DOWN

1
2
3
4
5
6
7
8
public static void solve() {
    int x = io.nextInt(), y = io.nextInt();
    if (y - x >= -3 && y - x <= 2) {
        io.println("Yes");
    } else {
        io.println("No");
    }
}

326-like Numbers

1
2
3
4
5
6
7
8
9
public static void solve() {
    int n = io.nextInt();
    for (; ; n++) {
        if (n / 100 * (n / 10 % 10) == n % 10) {
            io.println(n);
            return;
        }
    }
}

Peak

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    Arrays.sort(a);

    int ans = 0;
    for (int i = 0, j = 0; j < n; j++) {
        while (a[j] - a[i] >= m) {
            i++;
        }
        ans = Math.max(ans, j - i + 1);
    }
    io.println(ans);
}

ABC Puzzle

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
public static void solve() {
    int n = io.nextInt();
    char[] r = io.next().toCharArray();
    char[] c = io.next().toCharArray();

    int[] row = new int[n];
    int[] col = new int[n];
    char[][] ans = new char[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(ans[i], '.');
    }
    boolean ok = dfs(0, 0, r, c, ans, row, col, 0);

    if (!ok) {
        io.println("No");
        return;
    }
    io.println("Yes");
    for (int i = 0; i < n; i++) {
        io.println(new String(ans[i]));
    }
}

private static boolean dfs(int x, int y, char[] r, char[] c, char[][] ans, int[] row, int[] col, int cnt) {
    int n = r.length;
    if (x == n) {
        return cnt == 3 * n;
    }
    if (n - 1 - y >= 3 - Integer.bitCount(row[x])) {
        if (dfs(x + (y + 1) / n, (y + 1) % n, r, c, ans, row, col, cnt)) {
            return true;
        }
    }
    for (int i = 0; i < 3; i++) {
        if ((row[x] >> i & 1) == 1 || (col[y] >> i & 1) == 1) {
            continue;
        }
        if (row[x] == 0 && r[x] != 'A' + i) {
            continue;
        }
        if (col[y] == 0 && c[y] != 'A' + i) {
            continue;
        }
        row[x] |= 1 << i;
        col[y] |= 1 << i;
        ans[x][y] = (char) ('A' + i);
        if (dfs(x + (y + 1) / n, (y + 1) % n, r, c, ans, row, col, cnt + 1)) {
            return true;
        }
        row[x] ^= 1 << i;
        col[y] ^= 1 << i;
        ans[x][y] = '.';
    }
    return false;
}

Revenge of “The Salary of AtCoder Inc.”

概率 DP，答案为 \(\sum_{i=1}^{n}{A_{i}P_{i}}\)，而 \(P_{i}=\frac{1}{N}\sum_{j=0}^{i-1}{P_{j}}=P_{i-1}+\frac{1}{N}P_{i-1}\)。（这么简单，真没想到）

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 = 998244353;

public static void solve() {
    int n = io.nextInt();
    long invn = pow(n, MOD - 2);
    long ans = 0L, p = invn;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt();
        ans = (ans + p * a) % MOD;
        p = (p + invn * p) % MOD;
    }
    io.println(ans);
}

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;
}
发表更新基础 / 模板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\)，可以得到方程的解。

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×