消除相邻近似相等字符

题目

输入长度为 \(n\) 的字符串 \(s\)，输出所需的最少操作次数，使得字符串 \(s\) 中的相邻字符在字母表中的距离大于 \(1\)。每次操作可以将字符串 \(s\) 中的某个字符修改为任意字符。

数据范围：\(1\leq n\leq 100\)。

思路

思路一：距离大于 \(1\) 的相邻字符可以将字符串 \(s\) 分割为若干子串，每个子串所需的最少操作次数为 \(\lfloor\frac{l}{2}\rfloor\)，其中 \(l\) 表示子串的长度。

思路二：如果相邻字符距离小于等于 \(1\)，那么贪心的修改右边的字符即可。

两种思路原理是一样的，只是实现时略有不同。

关闭分部的可行集合数目

题目

输入整数 \(n\) 表示有 \(n\) 个节点，长度为 \(m\) 表示无向边的数组 \(e\)（包含重边），以及整数 \(d\)。输出删除节点的方案数，使得剩余节点两两之间的最短路不超过 \(d\)。

数据范围：\(1\leq n\leq 10\)，\(0\leq m\leq 1000\)。其他数据不会影响时间复杂度，所以不列出。

思路

题目要求满足条件的方案数，首先想到枚举所有方案，总共有 \(2^{n}\) 个方案，然后对每个方案求删除节点后的多源最短路（Floyd 算法），如果剩余节点两两之间的最短路都不超过 \(d\)，那么答案就加一，总时间复杂度为 \(O(m+2^{n}n^{3})\)。因为是求最短路，所以重边可以只保留最小的那条边。

需要添加的硬币的最小数量

题目

输入长度为 \(n\) 的数组 \(a\) 和整数 \(k\)，输出需要向数组插入多少个数，使得数组的子序列能够表示 \([1,k]\) 范围内的所有整数。

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

思路

从小到大遍历数组，假设当前能够表示的区间为 \([0,s]\)，此时遍历到数组中的数 \(a_{i}\)，我们可以表示区间 \([a_{i},s+a_{i}]\)。

• 如果 \(a_{i}\leq s+1\)，那么就可以合并两个区间，得到 \([0,s+a_{i}]\)，然后继续遍历 \(a_{i+1}\)。
• 否则，需要向数组插入数 \(s+1\) 来保证区间连续，得到 \([0,2s+1]\)，然后再次遍历 \(a_{i}\)。
• 不断重复上述过程直到能够表示区间 \([1,k]\)。

排序数组的时间复杂度为 \(O(n\log{n})\)，插入操作最多执行 \(O(\log{k})\) 次。

统计完全子字符串

题目

输入长度为 \(n\) 的由小写英文字母组成的字符串 \(s\) 和整数 \(k\)，输出满足以下两个条件的子字符串的个数。

• 每个字符恰好出现 \(k\) 次。
• 相邻字符在字母表中的距离小于等于 \(2\)。

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

思路

距离大于 \(2\) 的相邻字符可以将字符串分割成若干子串，对于每个子串 \(t\) 考虑满足条件一的子串 \(t_{i}\) 个数即可。我们可以枚举 \(t_{i}\) 包含多少个不同的字符（设为 \(x\)），对于每个 \(x\) 使用滑动窗口可以得到 \(t\) 中满足条件一的长度为 \(kx\) 的子串个数。时间复杂度为 \(O(|\Sigma| n)\)，外层循环执行 \(O(|\Sigma|)\) 次，内层循环滑窗执行 \(O(n)\) 次，滑窗的同时使用计数数组统计有多少个字符恰好出现 \(k\) 次，判断的时间复杂度为 \(O(1)\)。

统计感冒序列的数目

题目

输入整数 \(n\) 和长度为 \(m\) 的按照升序排列的数组 \(a\)，数组 \(a\) 存储下标 \([0,n-1]\) 的子序列，输出所有不在数组 \(a\) 中的下标被选择的方案数，答案对 \(10^{9}+7\) 取余。下标 \(i\) 可以被选择，当且仅当下标 \(i-1\) 或者 \(i+1\) 被选择，数组 \(a\) 中的下标可以看作是被选择的。

数据范围：\(2\leq n\leq 10^{5}\)，\(1\leq m\leq n-1\)，\(0\leq a_{i}\leq n-1\)。

思路

数组 \(a\) 中的下标将 \([0,n-1]\) 划分为多个子数组，首先考虑每个子数组内部的方案数：最左和最右的子数组只存在一种选择方案，其他子数组存在 \(2^{x_{i}-1}\) 种选择方案，\(x_{i}\) 为该子数组的长度。然后考虑子数组之间的方案数，最初我们有 \(n-m\) 个位置可以放置下标，假设各个子数组的长度分别为 \(x_{0},x_{1},\dots,x_{k}\)，那么总共有 \(\prod_{i=0}^{k}{C(n-m-\sum_{j=0}^{i-1}{x_{j}},x_{i})}=\frac{(n-m)!}{\prod_{i=0}^{k}{x_{i}!}}\) 种放置方案。将两者相乘即可得到答案，计算过程需要使用逆元和快速幂。

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

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