AtCoder Beginner Contest 312

Chord

简单模拟，比赛时打错了一个字母。

public static void solve() {
    String s = io.next();
    Set<String> set = Set.of("ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD");
    io.println(set.contains(s) ? "Yes" : "No");
}

TaK Code

因为左上角和右下角是中心对称的，所以判断右下角时可以使用形如 i + 8 - x 的下标来简化代码。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    String[] arr = new String[n];
    for (int i = 0; i < n; i++) arr[i] = io.next();
    for (int i = 0; i + 8 < n; i++) {
        for (int j = 0; j + 8 < m; j++) {
            boolean ok = true;
            for (int x = 0; x < 4; x++) {
                for (int y = 0; y < 4; y++) {
                    if (arr[i + x].charAt(j + y) != (x != 3 && y != 3 ? '#' : '.')) {
                        ok = false;
                    }
                    if (arr[i + 8 - x].charAt(j + 8 - y) != (x != 3 && y != 3 ? '#' : '.')) {
                        ok = false;
                    }
                }
            }
            if (ok) io.println((i + 1) + " " + (j + 1));
        }
    }
}

Invisible Hand

其实第一眼看到感觉是可以二分做的，不过比赛时使用的是两个优先队列模拟解决的，边界想了半天，结果最优解很妙啊。我们要求最小的 \(x\)，使得可能卖 \(x\) 元的卖家数量 \(f(x)\) 大于等于可能花 \(x\) 元买的买家数量 \(g(x)\)。其实我们要求的就是使 \(f(x)-g(x) >= 0\) 时的最小 \(x\)，而 \(f(x) - g(x)\) 是随 \(x\) 非严格递增的，当 \(x = 0\) 时，\(f(x)-g(x)=-M\)，并且答案的取值在 \(A_{1},\dots,A_{N},B_{1}+1,\dots,B_{M}+1\) 中，所以可以直接排序（或者快速选择），然后输出第 \(M\) 个数即为答案。

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] arr = new int[n + m];
    for (int i = 0; i < n; i++) arr[i] = io.nextInt();
    // 当价格大于买家的价格时，买家才会减一
    for (int i = 0; i < m; i++) arr[i + n] = io.nextInt() + 1;
    // 可以使用快速选择替换
    Arrays.sort(arr);
    io.println(arr[m - 1]);
}

Count Bracket Sequences

动态规划，不太会做。首先定义状态 \(dp[i][j]\)，表示区间 \([1,i]\) 中左括号比右括号多 \(j\) 个的方案数（也可以定义为其他形式）。然后写状态转移方程，可以画图看下转移方向，每层会分别向左下和右下转移 \(n\) 次，然后就可以写出不用特判边界的转移方程。还可以使用滚动数组优化空间，此处略过。

private static final int MOD = 998244353;

public static void solve() {
    String s = io.next();
    int n = s.length();
    // dp[i][j] 表示区间 [1, i] 中左括号比右括号多 j 个的方案数
    int[][] dp = new int[n + 1][n + 1];
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        char c = s.charAt(i - 1);
        for (int j = 0; j < n; j++) {
            if (c != ')') dp[i][j + 1] = dp[i - 1][j];
            if (c != '(') dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
        }
    }
    io.println(dp[n][0]);
}