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

Codeforces Round 915 (Div. 2)

Begginer’s Zelda

题目

输入一颗树，输出执行的最少操作次数，使得该树只有一个节点。每次操作可以选择树中的两个节点，将它们之间的路径压缩为一个节点，所有连接路径上节点的边都会连向新节点。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq u_{i},v_{i}\leq n\)，\(u_{i}\neq v_{i}\)。

思路

每次操作贪心的选择两个叶子节点（度数为 \(1\) 的节点都看作叶子），根据叶子节点的数量 \(x\) 的奇偶性分类讨论：

  • 如果 \(x\) 为奇数，\(x=1\) 需要 \(0\) 次操作，\(x=3\) 需要 \(2\) 次操作，之后每增加两个叶子，都会使操作次数加 \(1\)，由于数据范围限制初始时叶子至少有 \(2\) 个，所以操作次数为 \(\frac{x+1}{2}\)。
  • 如果 \(x\) 为偶数，\(x=2\) 需要 \(1\) 次操作，\(x=4\) 需要 \(2\) 次操作，之后每增加两个叶子，都会使操作次数加 \(1\)，所以操作次数为 \(\frac{x}{2}\)。
  • 最后，可以将两种情况的公式合并为 \(\lfloor\frac{x+1}{2}\rfloor\)。

Largest Subsequence

题目

输入长度为 \(n\) 的字符串 \(s\)，输出执行的最少操作次数，使得字符串有序。每次操作可以将字符串中字典序最大的子序列循环右移一位。

数据范围：\(1\leq n\leq 2\cdot 10^{5}\)。

思路

首先使用单调栈求出字典序最大的子序列（非严格单调递减），然后通过观察可以发现，执行多次操作最终会将该子序列反转。相当于求最少右移次数，使得子序列反转，该次数等于子序列长度减去子序列中最大字符的数量。其次，还需要判断子序列反转之后，字符串是否有序。

Cyclic MEX

题目

输入一个包含 \({0,1,2,\dots,n-1}\) 的排列 \(p\)，输出排列 \(p\) 的所有循环移动的最大代价。对于数组 \(a\)，它的代价为 \(\sum_{i=1}^{n}{\operatorname{mex}([a_{1},a_{2},\dots,a_{i}])}\)。

数据范围：\(1\leq n\leq 10^{5}\)。

思路

观察每循环左移一次，代价是如何变化的：

排列 \(2,3,6,7,0,1,4,5\) 对应的代价为 \(0,0,0,0,1,4,5,8\)；

排列 \(3,6,7,0,1,4,5,2\) 对应的代价为 \(0,0,0,1,2,2,2,8\)；

排列 \(6,7,0,1,4,5,2,3\) 对应的代价为 \(0,0,1,2,2,2,3,8\)。

可以发现每当将数 \(x\) 移动到排列末尾，所有大于 \(x\) 的 \(\operatorname{mex}\) 值都会变为 \(x\)，然后 \(x\) 位置对应的 \(\operatorname{mex}\) 值为 \(n\)。

我们可以首先将排列移动为 \(1,4,5,2,3,6,7,0\) 形式，对应的代价为 \(0,0,0,0,0,0,0,8\)。然后使用单调递增栈维护左移的数构成的递增序列，栈中存储数的下标，模拟上述过程并维护最大代价。

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

Codeforces Round 911 (Div. 2)

Cover in Water

只要存在三个连续的空格，就可以执行两次操作一，再多次执行操作二，来装满所有空格。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    String[] arr = s.split("#");
    int ans = 0;
    for (String t : arr) {
        int m = t.length();
        if (m >= 3) {
            io.println(2);
            return;
        }
        ans += m;
    }
    io.println(ans);
}

Laura and Operations

注意题目说的是剩下一种类型的数字，而不是一个数字。如果剩下数字 \(1\)，那么首先将 \(2\) 和 \(3\) 抵消，如果 \(2\) 多于 \(3\)，那么多出的数量如果是偶数，就可以将该数量的一半执行操作，再做一次抵消，最后就只剩下 \(1\)；反之亦然。

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    int a = io.nextInt(), b = io.nextInt(), c = io.nextInt();
    if (Math.abs(b - c) % 2 == 0) io.print(1);
    else io.print(0);
    io.print(" ");
    if (Math.abs(a - c) % 2 == 0) io.print(1);
    else io.print(0);
    io.print(" ");
    if (Math.abs(a - b) % 2 == 0) io.print(1);
    else io.print(0);
    io.println();
}

Anji’s Binary Tree

做一次后序遍历即可。题目说的是选择任意字母替换，而不是选择其他节点上的字母替换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    int[][] g = new int[n][];
    for (int i = 0; i < n; i++) {
        int l = io.nextInt() - 1, r = io.nextInt() - 1;
        g[i] = new int[]{l, r};
    }
    io.println(dfs(0, g, s));
}

private static int dfs(int x, int[][] g, String s) {
    if (g[x][0] == -1 && g[x][1] == -1) {
        return 0;
    }
    int res = Integer.MAX_VALUE;
    if (g[x][0] != -1) {
        res = Math.min(res, dfs(g[x][0],g, s) + (s.charAt(x) != 'L' ? 1 : 0));
    }
    if (g[x][1] != -1) {
        res = Math.min(res, dfs(g[x][1],g, s) + (s.charAt(x) != 'R' ? 1 : 0));
    }
    return res;
}

Small GCD

\(f(a,b,c)\) 表示 \(a,b,c\) 中最小的两个数的 \(\gcd\)，而我们要求出给定数组的所有不同下标构成的三元组的 \(f\) 之和。暴力的想法是枚举中间值，然后计算以该值为中心构成的三元组的 \(\gcd\) 之和，时间复杂度为 \(O(n^{2})\)。正确的做法：由于数据范围比较小，我们可以首先计算出 \([1,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
private static final int N = 100000;
private static final List<Integer>[] aux;

static {
    aux = new List[N + 1];
    Arrays.setAll(aux, k -> new ArrayList<>());
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            aux[j].add(i);
        }
    }
}

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    Arrays.sort(a);

    int[] c = new int[N + 1];
    long[] f = new long[N + 1];
    for (int i = 0; i < n; i++) {
        for (int x : aux[a[i]]) {
            f[x] += (long) c[x] * (n - i - 1);
            c[x]++;
        }
    }

    long ans = 0L;
    for (int i = N; i >= 1; i--) {
        for (int j = i + i; j <= N; j += i) {
            f[i] -= f[j];
        }
        ans += f[i] * i;
    }
    io.println(ans);
}

Transitive Graph

似乎是和强连通分量相关的题目，有空可以补一下。

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

Codeforces Round 908 (Div. 2)

Secret Sport

因为题目保证存在合法的 \(X\) 和 \(Y\)，那么获胜者总是最后一个下棋者，因为如果不是最后一个，那么对局就不会结束。

1
2
3
4
5
public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    io.println(s.charAt(n - 1));
}

Two Out of Three

对于一组相同元素，它只能满足一个条件，如果满足两个条件，那么它必定会满足三个条件。所以至少要有两组出现次数大于等于 \(2\) 的元素，然后分别让其满足一个条件即可。

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
public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }

    int k = 2;
    int[] b = new int[n];
    Arrays.fill(b, 1);
    int[] cnt = new int[101];
    for (int i = 0; i < n && k <= 3; i++) {
        if (++cnt[a[i]] == 2) {
            b[i] = k++;
        }
    }

    if (k <= 3) {
        io.println(-1);
        return;
    }
    for (int i = 0; i < n; i++) {
        io.print(b[i] + " ");
    }
    io.println();
}

Anonymous Informant

如果当前数组是通过移动得到，那么它的最后一个元素必定是由定点元素转移过来，所以我们只需要判断最后一个元素是否在 \([1,n]\) 范围内，然后不断地回滚左移操作，即不断地找到移动之前的最后一个元素位置，并进行判断即可。

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

    int i = n - 1;
    while (b[i] != -1 && b[i] < n && --k > 0) {
        int j = (i - (b[i] + 1) + n) % n;
        b[i] = -1;
        i = j;
    }
    io.println(k == 0 || b[i] == -1 ? "Yes" : "No");
}

Neutral Tonality

我们总是可以构造一个数组 \(c\)，使得 \(\operatorname{LIS}(c)=\operatorname{LIS}(a)\)，方法为将数组 \(b\) 中的元素 \(b_{i}\)，插入到数组 \(a\) 中第一个满足 \(a_{j}\leq b_{i}\) 的元素 \(a_{j}\) 之前，操作方式类似归并排序。

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
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();
    }
    var b = new Integer[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b, ((e1, e2) -> e2 - e1));

    int i = 0, j = 0, k = 0;
    int[] ans = new int[n + m];
    while (i < n || j < m) {
        if (i >= n) {
            ans[k++] = b[j++];
        } else if (j >= m) {
            ans[k++] = a[i++];
        } else if (a[i] <= b[j]) {
            ans[k++] = b[j++];
        } else {
            ans[k++] = a[i++];
        }
    }

    for (int x : ans) {
        io.print(x + " ");
    }
    io.println();
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×