AtCoder Beginner Contest 317

Potions

二分。

public static void solve() {
    int n = io.nextInt(), h = io.nextInt(), x = io.nextInt();
    int[] p = new int[n];
    for (int i = 0; i < n; i++) {
        p[i] = io.nextInt();
    }
    x = x - h;

    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (p[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    io.println(lo + 1);
}

MissingNo.

求和公式。

public static void solve() {
    int n = io.nextInt();
    int sum = 0;
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt();
        sum += a;
        min = Math.min(min, a);
        max = Math.max(max, a);
    }
    io.println((min + max) * (max - min + 1) / 2 - sum);
}

Remembering the Days

暴力 DFS。

private static int ans = Integer.MIN_VALUE;

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

    List<int[]>[] g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < m; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1, w = io.nextInt();
        g[u].add(new int[]{v, w});
        g[v].add(new int[]{u, w});
    }

    boolean[] vis = new boolean[n];
    for (int i = 0; i < n; i++) {
        dfs(i, 0, g, vis);
    }
    io.println(ans);
}

private static void dfs(int x, int dis, List<int[]>[] g, boolean[] vis) {
    vis[x] = true;
    ans = Math.max(ans, dis);
    for (int[] t : g[x]) {
        int y = t[0], w = t[1];
        if (!vis[y]) {
            dfs(y, dis + w, g, vis);
        }
    }
    vis[x] = false;
}

President

01 背包，比赛时转移方程弄错了一个细节，本来以为和答案是等价的，赛后改下就过了。

public static void solve() {
    int n = io.nextInt();
    int sum = 0;
    int[] x = new int[n];
    int[] y = new int[n];
    int[] z = new int[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        y[i] = io.nextInt();
        z[i] = io.nextInt();
        sum += z[i];
    }

    long[] dp = new long[sum + 1];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = sum; j >= z[i]; j--) {
            if (dp[j - z[i]] == Long.MAX_VALUE) continue;
            dp[j] = Math.min(dp[j], dp[j - z[i]] + Math.max(0, (y[i] - x[i] + 1) / 2));
        }
    }

    long ans = Long.MAX_VALUE;
    for (int i = (sum + 1) / 2; i <= sum; i++) {
        ans = Math.min(ans, dp[i]);
    }
    io.println(ans);
}

Avoid Eye Contact

模拟题，比赛时想复杂了，直接模拟就好。

public static void solve() {
    int h = io.nextInt(), w = io.nextInt();
    String[] a = new String[h];
    for (int i = 0; i < h; i++) {
        a[i] = io.next();
    }
    int s = -1, g = -1;
    boolean[][] mark = new boolean[h][w];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            char c = a[i].charAt(j);
            if (c == 'S') {
                s = i * w + j;
            } else if (c == 'G') {
                g = i * w + j;
            } else if (c == '#') {
                mark[i][j] = true;
            } else if (c == '^') {
                mark[i][j] = true;
                for (int k = i - 1; k >= 0 && a[k].charAt(j) == '.'; k--) {
                    mark[k][j] = true;
                }
            } else if (c == 'v') {
                mark[i][j] = true;
                for (int k = i + 1; k < h && a[k].charAt(j) == '.'; k++) {
                    mark[k][j] = true;
                }
            } else if (c == '<') {
                mark[i][j] = true;
                for (int k = j - 1; k >= 0 && a[i].charAt(k) == '.'; k--) {
                    mark[i][k] = true;
                }
            } else if (c == '>') {
                mark[i][j] = true;
                for (int k = j + 1; k < w && a[i].charAt(k) == '.'; k++) {
                    mark[i][k] = true;
                }
            }
        }
    }
    int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    int[] dis = new int[h * w];
    Arrays.fill(dis, -1);
    dis[s] = 0;
    Queue<Integer> q = new LinkedList<>();
    q.offer(s);
    while (!q.isEmpty()) {
        int z = q.poll();
        int x = z / w, y = z % w;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w || mark[nx][ny]) continue;
            int nz = nx * w + ny;
            if (dis[nz] != -1) continue;
            dis[nz] = dis[z] + 1;
            q.offer(nz);
        }
    }
    io.println(dis[g]);
}