Sort

题目

输入长度为 \(n\) 的数组 \(a\)，表示从 \(1\) 到 \(n\) 的排列。输出操作的次数和过程，使得排列有序。每次操作可以交换 \(a_{i}\) 和 \(a_{j}\)，其中 \(1\leq i<j\leq n\)。

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

思路

如果 \(a_{i}=i\)，则说明 \(a_{i}\) 在正确的位置上。否则，\(a_{i}\) 应该移动到位置 \(a_{i}\) 上，即交换下标 \(i\) 和 \(a_{i}\) 的值。这样每次交换都至少使得一个数在正确的位置上，最多交换 \(n-1\) 次，时间复杂度为 \(O(n)\)。PS：太久没做题，竟然没有做出来。比赛时多此一举，使用的是下标数组 + 排序做的，其实也没问题，就是最后没有按照大小顺序输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

    List<int[]> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        while (a[i] != i) {
            ans.add(new int[]{Math.min(i, a[i]), Math.max(i, a[i])});
            int t = a[a[i]]; a[a[i]] = a[i]; a[i] = t;
        }
    }

    io.println(ans.size());
    for (var t : ans) {
        io.println((t[0] + 1) + " " + (t[1] + 1));
    }
}

String Bags

题目

输入字符串 \(T\) 和整数 \(N\)，表示有 \(N\) 个袋子。然后对每个袋子，输入其包含的字符串个数 \(A_{i}\)，以及 \(A_{i}\) 个字符串 \(S_{i,1},S_{i,2},\dots,S_{i,A_{i}}\)。对于每个袋子，我们只能从中选择一个字符串或者不选。输出选择袋子的最少个数，使得按照袋子的编号顺序拼接字符串，能够得到字符串 \(T\)。如果无法得到字符串 \(T\)，则输出 \(-1\)。

数据范围：\(1\leq \operatorname{len}(T)\leq 100\)，\(1\leq N\leq 100\)，\(1\leq A_{i}\leq 10\)，\(1\leq \operatorname{len}(S_{i,j})\leq 10\)。

思路

定义 \(dp[i][j]\) 表示从袋子 \([1,i]\) 中选择袋子的最少个数，使得拼接得到的字符串和 \(T\) 的前缀 \([1,j]\) 相同（下标从 \(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

public static void solve() {
    String t = io.next();
    int n = io.nextInt();

    int m = t.length();
    int[] dp = new int[m + 1];
    Arrays.fill(dp, m + 1);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        int z = io.nextInt();
        Set<String> set = new HashSet<>();
        for (int j = 0; j < z; j++) {
            set.add(io.next());
        }

        for (int j = m - 1; j >= 0; j--) {
            for (int k = 1; k <= 10 && k <= j + 1; k++) {
                if (set.contains(t.substring(j - k + 1, j + 1))) {
                    dp[j + 1] = Math.min(dp[j + 1], dp[j + 1 - k] + 1);
                }
            }
        }
    }
    io.println(dp[m] == m + 1 ? -1 : dp[m]);
}

Non-Decreasing Colorful Path

题目

输入有 \(n\) 个顶点和 \(m\) 条边的连通的无向图（没有重边和自环），每个顶点上有一个整数 \(A_{i}\)，输出所有从顶点 \(1\) 到 \(N\) 的简单路径的最高得分。如果路径中顶点上的整数构成的序列非递减，那么该路径的得分为序列中不同整数的个数，否则得分为 \(0\)。

数据范围：\(2\leq n\leq 2 \times 10^{5}\)，\(1\leq A_{i}\leq 2\times 10^{5}\)。

思路

虽然是无向图，但是序列需要非递减才能有得分。进一步观察可以发现，对于一条非递减路径，所有包含相同整数的顶点只会贡献 \(1\) 个得分，我们可以将这些顶点缩为一个顶点。所以，只需要建立满足递增条件的有向边，如果边的两个顶点包含相同的整数，则使用并查集将它们连接（缩点）。然后问题就变为求 DAG 中两个顶点之间的最长路径，不过和一般的使用拓扑排序 + 动态规划来求解的方式不同，因为缩点的缘故，该题不是很好使用拓扑排序。由于 \(A_{i}\) 的范围比较小，从小到大枚举顶点整数，然后扩展以该整数为起点的边，结合动态规划可以比较方便的求出答案。实现时，需要注意起点和终点同样可能被缩点，使用时将其替换为并查集中所在连通块的根节点。