Pinely Round 2 (Div. 1 + Div. 2)

Channel

如果同时在线人数到达 \(n\)，就表示所有人都阅读过；否则，如果总上线人数大于等于 \(n\)，则有可能所有人阅读过；否则，不可能所有人阅读过。

public static void solve() {
    int n = io.nextInt(), a = io.nextInt(), q = io.nextInt();
    String s = io.next();
    int cur = a, tot = a;
    for (int i = 0; i < q && cur < n; i++) {
        if (s.charAt(i) == '+') {
            cur++;
            tot++;
        } else {
            cur--;
        }
    }
    if (cur == n) {
        io.println("YES");
    } else if (tot >= n) {
        io.println("MAYBE");
    } else {
        io.println("NO");
    }
}

Split Sort

对于每个 \(p_{i}=k+1\) 和 \(p_{j}=k\) 并且 \(i<j\)，那么就一定要选一次 \(x=k+1\)。

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

MEX Repetition

每执行一次操作，就会去除最后一个数，并将 \(MEX\) 添加到序列头部。所以可以通过在数组末尾加上原始数组的 \(MEX\)，将操作看成是向左移动循环数组的起始索引。求原始数组的 \(MEX\) 可以使用求和公式。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    long sum = 0L;
    int[] a = new int[n + 1];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        sum += a[i];
    }
    a[n] = (int) ((long) (1 + n) * n / 2 - sum);
    k = k % (n + 1);
    for (int i = 0; i < n; i++) {
        io.print(a[(-k + n + 1 + i) % (n + 1)] + " ");
    }
    io.println();
}

Two-Colored Dominoes

横放的牌只会对列有影响，竖放的牌只会对行有影响，所以分别处理。按行遍历竖放的牌，每当遇到 \(U\) 就染上和上次相反的颜色，如果该行只包含奇数个 \(U\)，就返回 \(-1\)。横放的牌同理。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    char[][] s = new char[n][];
    for (int i = 0; i < n; i++) {
        s[i] = io.next().toCharArray();
    }
    final char[] aux = {'B', 'W'};
    for (int i = 0; i < n - 1; i++) {
        int xor = 0;
        for (int j = 0; j < m; j++) {
            if (s[i][j] == 'U') {
                s[i][j] = aux[xor];
                s[i + 1][j] = aux[xor ^ 1];
                xor ^= 1;
            }
        }
        if (xor != 0) {
            io.println(-1);
            return;
        }
    }
    for (int j = 0; j < m - 1; j++) {
        int xor = 0;
        for (int i = 0; i < n; i++) {
            if (s[i][j] == 'L') {
                s[i][j] = aux[xor];
                s[i][j + 1] = aux[xor ^ 1];
                xor ^= 1;
            }
        }
        if (xor != 0) {
            io.println(-1);
            return;
        }
    }
    for (int i = 0; i < n; i++) {
        io.println(new String(s[i]));
    }
}

Speedrun

其实思路是知道的，就是不知道怎么写。这个解法看着有点懵，可能其他解法会更好理解一点。注意题目给定 \(a_{i}<b_{i}\)。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), k = io.nextInt();
    int[] h = new int[n];
    for (int i = 0; i < n; i++) {
        h[i] = io.nextInt();
    }
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, idx -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int a = io.nextInt() - 1, b = io.nextInt() - 1;
        g[a].add(b);
    }
    // dp[i] 表示完成所有依赖第 i 个任务的任务需要的时间（从 h[i] 开始）
    long[] dp = new long[n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j : g[i]) {
            dp[i] = Math.max(dp[i], dp[j] + (h[j] - h[i] + k) % k);
        }
    }
    // dp[i] 表示完成所有依赖第 i 个任务的任务需要的时间（从零开始）
    long max = 0L;
    for (int i = 0; i < n; i++) {
        dp[i] += h[i];
        max = Math.max(max, dp[i]);
    }
    // 按照 h[i] 的大小，从小到大枚举起点
    Integer[] aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> h[i] - h[j]);
    long ans = Long.MAX_VALUE;
    for (int i : aux) {
        ans = Math.min(ans, max - h[i]);
        // 如果起点大于 h[i]，那么任务 i 的完成时间需要加 k，从而导致 dp[i] + k
        // 其实只要枚举入度为 0 的任务就行，但是即使任务 i 不是入度为 0 任务也没有关系，因为对答案没有影响
        max = Math.max(max, dp[i] + k);
    }
    io.println(ans);
}