Educational Codeforces Round 156 (Rated for Div. 2)

Sum of Three

当 n <= 6 || n == 9 时，不能凑出三个不同的不能被 \(3\) 整除的正整数，其他情况均可以通过以下方式凑出。

public static void solve() {
    int n = io.nextInt();
    if (n <= 6 || n == 9) {
        io.println("NO");
        return;
    }
    int a = 1, b = 2, c = n - 3;
    if (c % 3 == 0) {
        c -= 2;
        b += 2;
    }
    io.println("YES");
    io.println(a + " " + b + " " + c);
}

Fear of the Dark

可以分为四种情况：点 \(O\) 和 点 \(P\) 在圆 \(A\) 内/上；点 \(O\) 和 点 \(P\) 在圆 \(B\) 内/上；点 \(O\) 和 点 \(P\) 分别在圆 \(A\) 和圆 \(B\) 内/上，并且圆 \(A\) 和圆 \(B\) 相切/相交；点 \(O\) 和 点 \(P\) 分别在圆 \(B\) 和圆 \(A\) 内/上，并且圆 \(A\) 和圆 \(B\) 相切/相交。

方法一：浮点二分

public static void solve() {
    double px = io.nextInt(), py = io.nextInt();
    double ax = io.nextInt(), ay = io.nextInt();
    double bx = io.nextInt(), by = io.nextInt();

    double lo = 0, hi = 1e4;
    while (hi - lo > 1e-9) {
        double mid = lo + (hi - lo) / 2;
        boolean oToA = dist(0, 0, ax, ay) <= mid;
        boolean aToP = dist(ax, ay, px, py) <= mid;
        boolean oToB = dist(0, 0, bx, by) <= mid;
        boolean bToP = dist(bx, by, px, py) <= mid;
        boolean aToB = dist(ax, ay, bx, by) <= 2 * mid;
        if ((oToA && aToP) || (oToB && bToP) || (oToA && aToB && bToP) || (oToB && aToB && aToP)) hi = mid;
        else lo = mid;
    }
    io.println(hi);
}

private static double dist(double x1, double y1, double x2, double y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

方法二：直接计算

public static void solve() {
    double px = io.nextInt(), py = io.nextInt();
    double ax = io.nextInt(), ay = io.nextInt();
    double bx = io.nextInt(), by = io.nextInt();

    double oToA = dist(0, 0, ax, ay);
    double aToP = dist(ax, ay, px, py);
    double oToB = dist(0, 0, bx, by);
    double bToP = dist(bx, by, px, py);
    double aToB = dist(ax, ay, bx, by);

    double ans = Math.max(oToA, aToP);
    ans = Math.min(ans, Math.max(oToB, bToP));
    ans = Math.min(ans, Math.max(oToA, Math.max(aToB / 2, bToP)));
    ans = Math.min(ans, Math.max(oToB, Math.max(aToB / 2, aToP)));
    io.println(ans);
}

private static double dist(double x1, double y1, double x2, double y2) {
    return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

Decreasing String

二分删除的字符数 \(p\)，可以通过计算得到 \(q=pos-\frac{(n+(n-p+1))\cdot p}{2}\)，则答案为 \(s_{1+p}[q]\)，可以使用单调栈删除字符，然后获取答案即可。

public static void solve() {
    String s = io.next();
    long pos = io.nextLong();

    int n = s.length();
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if ((long) (n + n - mid + 1) * mid / 2 < pos) lo = mid + 1;
        else hi = mid - 1;
    }
    int p = hi, q = (int) (pos - (long) (n + n - hi + 1) * hi / 2);

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n; i++) {
        while (p > 0 && !sb.isEmpty() && sb.charAt(sb.length() - 1) > s.charAt(i)) {
            sb.deleteCharAt(sb.length() - 1);
            p--;
        }
        sb.append(s.charAt(i));
    }
    io.print(sb.charAt(q - 1));
}

Monocarp and the Set

很容易想到当 s[0] == '?' 时，方案数为 \(0\)，并且 > 和 < 符号的位置放什么数都是确定的，也就是说只有 ? 位置对答案有贡献。分别考虑每个 ? 位置（从位置 \(1\) 开始，因为位置 \(0\) 不能是 ?），假设该位置的下标为 \(i\)，那么它是第 \(i+2\) 个的数（因为添加第 \(1\) 个数时，不会记录字符到 \(s\) 中，并且下标从 \(0\) 开始，所以加 \(2\)），第 \(i+2\) 个数必须要大于前 \(i+1\) 个数的最小值，小于前 \(i+1\) 个数的最大值。我们可以将前 \(i+1\) 个数排成有序的序列，然后根据大小将第 \(i+2\) 个数插入到序列中，总共有 \(i+2\) 个插入位置，但在限制条件下，我们只能选择 \(i\) 个位置进行插入，对所有 ? 位置累乘 \(i\) 即可得到当前字符串的插入方案数。

看半天才懂，很多题解只提到插入法，根本没提到有序序列，只要知道是根据大小插入就很简单了。也就是说，插入时根本不关心当前是什么数，只关心当前数在前面数的最大值和最小值之间。在将所有的数插入完成后，所有 ? 位置是什么数就随之确定，也就确定了一种方案。

private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    char[] s = io.next().toCharArray();

    long ans = 1L;
    for (int i = 1; i < n - 1; i++) {
        if (s[i] == '?') ans = ans * i % MOD;
    }

    query(s, ans);
    while (m-- != 0) {
        int i = io.nextInt() - 1;
        char c = io.next().charAt(0);
        if (i != 0 && s[i] == '?') {
            ans = ans * pow(i, MOD - 2) % MOD;
        }
        s[i] = c;
        if (i != 0 && s[i] == '?') {
            ans = ans * i % MOD;
        }
        query(s, ans);
    }
}

private static void query(char[] s, long ans) {
    if (s[0] == '?') io.println(0);
    else io.println(ans);
}

private static int pow(int a, int n) {
    long res = 1L, x = a;
    while (n != 0) {
        if ((n & 1) == 1) res = res * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return (int) res;
}