Codeforces Round 891 (Div. 3)

Array Coloring

要将数组分为奇偶性相同的两部分，那么奇数的个数一定要是偶数。

public static void solve() {
    int n = io.nextInt(), sum = 0;
    for (int i = 0; i < n; i++) {
        sum += io.nextInt();
    }
    io.println(sum % 2 == 0 ? "YES" : "NO");
}

Maximum Rounding

题目有点难读，其实就是大于等于 \(5\) 的数可以向前进位，并且包括自己在内的所有低位全部置为 \(0\)。

public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length, c = 0, p = n;
    for (int i = n - 1; i > 0; i--) {
        if (s[i] >= '5') {
            s[i - 1]++;
            p = i;
        }
    }
    if (s[0] >= '5') io.println("1" + "0".repeat(n));
    else io.println(new String(s, 0, p) + "0".repeat(n - p));
}

Assembly via Minimums

对数组排序，最小值会出现 \(n - 1\) 次，次小值会出现 \(n - 2\) 次，以此类推，次大值出现 \(1\) 次，最大值出现 \(0\) 次，所以最后需要补一个最大值。

public static void solve() {
    int n = io.nextInt(), m = n * (n - 1) / 2;
    int[] b = new int[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b);
    for (int i = 0; i < m; i += --n) {
        io.print(b[i] + " ");
    }
    io.println(b[m - 1]);
}

Strong Vertices

将公式变形，易知 \(a_{u} - b_{u}\) 的值最大的元素是强壮的。

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    int max = Integer.MIN_VALUE, cnt = 0;
    for (int i = 0; i < n; i++) {
        a[i] -= io.nextInt();
        if (a[i] > max) {
            max = a[i];
            cnt = 1;
        } else if (a[i] == max) {
            cnt++;
        }
    }
    io.println(cnt);
    for (int i = 0; i < n; i++) {
        if (a[i] == max) {
            io.print(i + 1 + " ");
        }
    }
    io.println();
}

Power of Points

对于每个 \(x_{i}\) 构成的区间，\(\sum_{p=1}^{10^9}f_{p}\) 表示所有区间包含的元素的个数的和。暴力计算的时间复杂度是 \(O(n^{2})\)，但是我们可以考虑 \(x\) 从从小到大转移时，元素个数的变化量，从而使用 \(O(n\log n)\) 的时间复杂度计算出所有答案。（也可以像官解一样推公式）

public static void solve() {
    int n = io.nextInt();
    long sum = 0L;
    int[] x = new int[n];
    Integer[] aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        sum += x[i];
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> x[i] - x[j]);
    long[] ans = new long[n];
    ans[aux[0]] = sum -= (long) n * (x[aux[0]] - 1);
    for (int k = 1; k < n; k++) {
        sum += (long) (k - (n - k)) * (x[aux[k]] - x[aux[k - 1]]);
        ans[aux[k]] = sum;
    }
    for (long s : ans) io.print(s + " ");
    io.println();
}

Sum and Product

解方程。。因为要求是整数解，所以根号下必须是完全平方数。还有要注意 \(\Delta\) 小于零的情况，不过 Java 的开根函数在小于零的情况下会返回 NaN，转成整数就是零，在该题目的判断中不会引发问题，但还是最好特判一下。

public static void solve() {
    int n = io.nextInt();
    Map<Long, Integer> map = new HashMap<>();
    for (int i = 0; i < n; i++) {
        map.merge((long) io.nextInt(), 1, Integer::sum);
    }
    int q = io.nextInt();
    for (int i = 0; i < q; i++) {
        long x = io.nextInt(), y = io.nextLong();
        long d = x * x - 4 * y, s = (long) Math.sqrt(d);
        if (d < 0 || s * s != d) {
            io.print(0 + " ");
            continue;
        }
        long c1 = map.getOrDefault((x + s) / 2, 0);
        long c2 = map.getOrDefault((x - s) / 2, 0);
        if (s != 0) io.print(c1 * c2 + " ");
        else io.print(c1 * (c1 - 1) / 2 + " ");
    }
    io.println();
}

Counting Graphs

如果要在 \(u\) 和 \(v\) 之间添加一条边，那么首先要求 \(u\) 和 \(v\) 之间没有直接相连的边，并且新添加的边的权重要大于 \(w\) 小于 \(S\)，这样才能保证最小生成树是给定的树。暴力求解的时间复杂度是 \(O(n^{2})\)，我们可以利用 Kruskal 算法优化，对边按权重从小到大排序，然后在连接两个顶点时计算两棵树之间顶点连接的方案数，将所有计算结果相乘就是答案。

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt(), S = io.nextInt();
    List<int[]> edges = new ArrayList<>();
    for (int i = 0; i < n - 1; i++) {
        int u = io.nextInt(), v = io.nextInt(), w = io.nextInt();
        edges.add(new int[]{u, v, w});
    }
    edges.sort((a, b) -> a[2] - b[2]);
    long ans = 1L;
    UnionFind uf = new UnionFind(n + 1);
    for (int[] e : edges) {
        int u = e[0], v = e[1], w = e[2];
        ans = (ans * fastPower(S - w + 1, (long) uf.size(u) * uf.size(v) - 1)) % MOD;
        uf.union(u, v);
    }
    io.println(ans);
}