Codeforces Round 897 (Div. 2)

green_gold_dog, array and permutation

让最小值减去最大值，就一定可以得到 \(n\) 个不同的差值。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    var aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> a[i] - a[j]);
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        int t = aux[i];
        ans[t] = n - i;
    }
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

XOR Palindromes

算是简单的分类讨论，比赛时写的稀烂。

public static void solve() {
    int n = io.nextInt(), cnt = 0;
    char[] s = io.next().toCharArray();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            cnt++;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i <= n; i++) {
        if (i < cnt || i > n - cnt || (i - cnt) % 2 == 1 && n % 2 == 0) {
            sb.append('0');
        } else {
            sb.append('1');
        }
    }
    io.println(sb);
}

Salyg1n and the MEX Game

比赛调试一小时，疯狂超时，结果是限制太强的原因。（浪费时间。）

public static void solve() {
    int n = io.nextInt();
    int[] s = new int[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.nextInt();
    }
    Arrays.sort(s);
    int x = n;
    for (int i = 0; i < n ; i++) {
        if (s[i] != i) {
            x = i;
            break;
        }
    }
    while (x != -1) {
        io.println(x);
        io.flush();
        x = io.nextInt();
    }
}

Cyclic Operations

做了一个多小时 AC，有点像之前做的内向基环树，该题每个点都有个出边，所以至少有一个环。首先要特判 \(k=1\) 的情况，该情况每个位置都必须自成一个环，即 \(a_{i}=i\)；其他情况所有环的长度都必须为 \(k\)，这样可以保证答案存在。

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[] in = new int[n];
    for (int i = 0; i < n; i++) {
        in[b[i]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            q.offer(i);
        }
    }
    while (!q.isEmpty()) {
        int x = q.poll();
        if (--in[b[x]] == 0) {
            q.offer(b[x]);
        }
    }

    int cnt = 0;
    boolean[] vis = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (in[i] == 0 || vis[i]) continue;
        int len = 0;
        for ( ; !vis[i]; i = b[i]) {
            vis[i] = true;
            len++;
        }
        if (len != k) {
            io.println("NO");
            return;
        }
        cnt++;
    }
    if (k == 1 && cnt != n) {
        io.println("NO");
    } else {
        io.println("YES");
    }
}

Salyg1n and Array (simple version)

注意，\(n\) 和 \(k\) 都是偶数！手推的话可能可以做出来吧。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    int ans = 0, i;
    for (i = 1; i + k - 1 <= n; i += k) {
        io.println("? " + i);
        io.flush();
        ans ^= io.nextInt();
    }
    for (; i <= n; i++) {
        io.println("? " + (i - k + 1));
        io.flush();
        ans ^= io.nextInt();
    }
    io.println("! " + ans);
    io.flush();
}

Salyg1n and Array (hard version)

技巧性有点强，真想不到。就是如果多出一部分，可以通过两次异或算出来。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    int ans = 0, i;
    for (i = 1; i + k - 1 <= n; i += k) {
        io.println("? " + i);
        io.flush();
        ans ^= io.nextInt();
    }
    int t = n - i + 1;
    io.println("? " + (n - k + 1 - t / 2));
    io.flush();
    ans ^= io.nextInt();
    io.println("? " + (n - k + 1));
    io.flush();
    ans ^= io.nextInt();
    io.println("! " + ans);
    io.flush();
}