Codeforces Round 893 (Div. 2)

Buttons

优先选择公共按钮，当且仅当先手的按钮数量大于后手的按钮数量时，先手者胜。

public static void solve() {
    int a = io.nextInt(), b = io.nextInt(), c = io.nextInt();
    if (a + c % 2 > b) io.println("First");
    else io.println("Second");
}

The Walkway

模拟题，特别需要注意头尾的边界处理，加上哨兵真的会方便很多。可以假设位置 \(1-d\) 和位置 \(n+1\) 有卖家，这样就不用特判，可以直接处理！！！

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

    int ans = m - 1, delta = Integer.MAX_VALUE, cnt = 0;
    for (int i = 1; i <= m; i++) {
        int A = (s[i] - s[i - 1] - 1) / d;
        int B = (s[i + 1] - s[i] - 1) / d;
        int C = (s[i + 1] - s[i - 1] - 1) / d;
        int D = C - A - B;

        if (D < delta) {
            delta = D;
            cnt = 1;
        } else if (D == delta) {
            cnt++;
        }
        ans += A;
    }
    ans += (s[m + 1] - s[m] - 1) / d + delta - 1;
    io.println(ans + " " + cnt);
}

Yet Another Permutation Problem

构造题，首先需要发现什么公约数不可能出现，很明显不可能得到 \(d_{i}=\gcd (a_{i},a_{(i\bmod n)+1})> \lfloor \frac{n}{2}\rfloor\)。然后考虑所有小于等于 \(\lfloor \frac{n}{2}\rfloor\) 的数是否能被包含，可以发现对于每个 \(a_{i}=x\leq \lfloor \frac{n}{2}\rfloor\) 总有 \(a_{(i\bmod n)+1}=2\cdot x\leq n\)，所以我们可以枚举所有奇数乘以二的幂来构造答案。

public static void solve() {
    int n = io.nextInt(), idx = 0;
    int[] ans = new int[n];
    for (int i = 1; i <= n; i += 2) {
        for (int j = i; j <= n; j *= 2) {
            ans[idx++] = j;
        }
    }
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

Trees and Segments

难以描述，看代码吧，调试半天。。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    char[] s = io.next().toCharArray();
    int[][] prefix = new int[n + 1][k + 1];
    int[][] suffix = new int[n + 1][k + 1];
    // 枚举可以在 k 次操作内变为全 0 的子数组，并将其长度记录到所属的前后缀中
    for (int i = 0; i < n; i++) {
        int cnt1 = 0;
        for (int j = i; j < n; j++) {
            cnt1 += s[j] - '0';
            if (cnt1 > k) break;
            prefix[j + 1][cnt1] = Math.max(prefix[j + 1][cnt1], j - i + 1);
            suffix[i][cnt1] = Math.max(suffix[i][cnt1], j - i + 1);
        }
    }
    // 在前缀 [0, i] 中最多操作 j 次，可以得到的连续 0 的最长长度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            prefix[i + 1][j] = Math.max(prefix[i + 1][j], prefix[i][j]);
            if (j > 0) prefix[i + 1][j] = Math.max(prefix[i + 1][j], prefix[i + 1][j - 1]);
        }
    }
    // 在后缀 [i, n - 1] 中最多操作 j 次，可以得到的连续 0 的最长长度
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= k; j++) {
            suffix[i][j] = Math.max(suffix[i][j], suffix[i + 1][j]);
            if (j > 0) suffix[i][j] = Math.max(suffix[i][j], suffix[i][j - 1]);
        }
    }
    // 枚举连续 1 的起点和终点，并记录该连续 1 的长度对应的连续 0 的最长长度（注意包含长度为 0 的情况）
    int[] max0by1 = new int[n + 1];
    Arrays.fill(max0by1, -1);
    max0by1[0] = suffix[0][k];
    for (int i = 0; i < n; i++) {
        int cnt0 = 0;
        for (int j = i; j < n; j++) {
            cnt0 += (s[j] - '0') ^ 1;
            if (cnt0 > k) break;
            max0by1[j - i + 1] = Math.max(max0by1[j - i + 1], prefix[i][k - cnt0]);
            max0by1[j - i + 1] = Math.max(max0by1[j - i + 1], suffix[j + 1][k - cnt0]);
        }
    }
    // 计算答案
    int[] ans = new int[n + 1];
    for (int a = 1; a <= n; a++) {
        for (int i = 0; i <= n; i++) {
            if (max0by1[i] == -1) continue;
            ans[a] = Math.max(ans[a], i + max0by1[i] * a);
        }
    }
    for (int i = 1; i <= n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}