AtCoder Beginner Contest 322

First ABC 2

public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    int ans = s.indexOf("ABC");
    io.println(ans < 0 ? -1 : ans + 1);
}

Prefix and Suffix

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    String s = io.next(), t = io.next();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) != t.charAt(i)) {
            ans |= 2;
        }
        if (s.charAt(i) != t.charAt(m - n + i)) {
            ans |= 1;
        }
    }
    io.println(ans);
}

Festival

public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    for (int i = 0; i < m; i++) {
        int x = io.nextInt() - 1;
        ans[x] = 0;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ans[i] == -1) {
            ans[i] = ans[i + 1] + 1;
        }
    }
    for (int i = 0; i < n; i++) {
        io.println(ans[i]);
    }
}

Polyomino

模拟题，使用位运算似乎更简单，题解。

public static void solve() {
    char[][][] G = new char[3][4][4];
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 4; j++) {
            G[i][j] = io.next().toCharArray();
        }
    }
    io.println(dfs(0, G, new char[4][4]) ? "Yes" : "No");
}

private static boolean dfs(int i, char[][][] G, char[][] C) {
    if (C == null) return false;
    if (i == 3) return check(C);
    for (int j = 0; j < 4; j++) {
        for (int dx = -3; dx <= 3; dx++) {
            for (int dy = -3; dy <= 3; dy++) {
                char[][] T = move(dx, dy, G[i]);
                if (T == null) continue;
                if (dfs(i + 1, G, add(T, C))) return true;
            }
        }
        G[i] = rotate(G[i]);
    }
    return false;
}

private static char[][] rotate(char[][] A) {
    char[][] B = new char[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            B[i][j] = A[3 - j][i];
        }
    }
    return B;
}

private static char[][] move(int dx, int dy, char[][] G) {
    char[][] res = new char[4][4];
    for (int i = 0; i < 4; i++) {
        Arrays.fill(res[i], '.');
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            int nx = i + dx, ny = j + dy;
            if(G[i][j] == '#') {
                if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) {
                    return null;
                }
                res[nx][ny] = G[i][j];
            }
        }
    }
    return res;
}

private static char[][] add(char[][] T, char[][] C) {
    char[][] res = new char[4][4];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (C[i][j] == '#' && T[i][j] == '#') return null;
            if (C[i][j] == '#' || T[i][j] == '#') res[i][j] = '#';
            else res[i][j] = '.';
        }
    }
    return res;
}

private static boolean check(char[][] C) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (C[i][j] != '#') return false;
        }
    }
    return true;
}

Product Development

动态规划，\(dp[i][j]\) 表示从前 \(i\) 个计划中选择开发计划，使得参数到达 \(j\)，需要的最小成本，其中 \(j\) 表示 \(a_{1},a_{2},\dots,a_{k}\) 的某个取值，通过将序列看作 \(p+1\) 进制数，可以将一个序列转换为某个数值（在这里就是 \(j\)）。

public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), p = io.nextInt();

    int[] pw = new int[k + 1];
    pw[0] = 1;
    for (int i = 1; i <= k; i++) {
        pw[i] = pw[i - 1] * (p + 1);
    }

    long[] dp = new long[pw[k]];
    Arrays.fill(dp, -1L);
    dp[0] = 0;

    for (int i = 0; i < n; i++) {
        int c = io.nextInt();
        int[] a = new int[k];
        for (int j = 0; j < k; j++) {
            a[j] = io.nextInt();
        }

        for (int s = pw[k] - 1; s >= 0; s--) {
            int t = 0;
            for (int j = 0; j < k; j++) {
                int cur = s / pw[j] % (p + 1);
                int nxt = Math.min(p, cur + a[j]);
                t += nxt * pw[j];
            }
            if (dp[s] != -1 && (dp[t] == -1 || dp[t] > dp[s] + c)) {
                dp[t] = dp[s] + c;
            }
        }
    }
    io.println(dp[pw[k] - 1]);
}