发表更新算法 / AtCoder4 分钟读完 (大约589个字)

AtCoder Beginner Contest 320

Leyland Number

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
public static void solve() {
    int a = io.nextInt(), b = io.nextInt();
    int x = 1;
    for (int i = 0; i < b; i++) {
        x *= a;
    }
    int y = 1;
    for (int i = 0; i < a; i++) {
        y *= b;
    }
    io.println(x + y);
}

Longest Palindrome

模拟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    String s = io.next();
    int n = s.length();
    int ans = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            String a = s.substring(i, j + 1);
            String b = new StringBuilder(a).reverse().toString();
            if (a.equals(b)) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    io.println(ans);
}

Slot Strategy 2 (Easy)

暴力枚举每个转盘的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void solve() {
    int n = 3, m = io.nextInt();
    int ans = Integer.MAX_VALUE;
    String[] s = new String[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.next();
    }
    for (int i = 0; i < n * m; i++) {
        char a = s[0].charAt(i % m);
        for (int j = 0; j < n * m; j++) {
            if (i == j) continue;
            char b = s[1].charAt(j % m);
            for (int k = 0; k < n * m; k++) {
                if (i == k || j == k) continue;
                char c = s[2].charAt(k % m);
                if (a == b && b == c) {
                    ans = Math.min(ans, Math.max(i, Math.max(j, k)));
                }
            }
        }
    }
    io.println(ans == Integer.MAX_VALUE ? -1 : ans);
}

Relative Position

DFS 模拟，需要注意给的不是一棵树，所以在 DFS 时要使用访问数组，而不能用父结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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 a = io.nextInt() - 1, b = io.nextInt() - 1, x = io.nextInt(), y = io.nextInt();
        g[a].add(new int[]{b, x, y});
        g[b].add(new int[]{a, -x, -y});
    }
    long[] X = new long[n];
    long[] Y = new long[n];
    Arrays.fill(X, Long.MAX_VALUE);
    Arrays.fill(Y, Long.MAX_VALUE);
    boolean[] vis = new boolean[n];
    dfs(0, vis, g, 0, 0, X, Y);
    for (int i = 0; i < n; i++) {
        if (X[i] != Long.MAX_VALUE && Y[i] != Long.MAX_VALUE) {
            io.println(X[i] + " " + Y[i]);
        } else {
            io.println("undecidable");
        }
    }
}

private static void dfs(int i, boolean[] vis, List<int[]>[] g, long x, long y, long[] X, long[] Y) {
    X[i] = x;
    Y[i] = y;
    vis[i] = true;
    for (int[] t : g[i]) {
        int j = t[0];
        if (vis[j]) continue;
        long nx = t[1] + x, ny = t[2] + y;
        dfs(j, vis, g, nx, ny, X, Y);
    }
}

Somen Nagashi

还是模拟，可以一边输入一边处理，减少代码量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    long[] ans = new long[n], re = new long[n];
    PriorityQueue<Integer> q = new PriorityQueue<>();
    PriorityQueue<Integer> p = new PriorityQueue<>((a, b) -> Long.compare(re[a], re[b]));
    for (int i = 0; i < n; i++) {
        q.offer(i);
    }
    while (m-- != 0) {
        int t = io.nextInt(), w = io.nextInt(), s = io.nextInt();
        while (!p.isEmpty() && re[p.peek()] <= t) q.offer(p.poll());
        if (q.isEmpty()) continue;
        int x = q.peek();
        ans[x] += w;
        re[x] = t + s;
        p.offer(q.poll());
    }
    for (int i = 0; i < n; i++) {
        io.println(ans[i]);
    }
}
发表更新算法 / AtCoder5 分钟读完 (大约810个字)

AtCoder Beginner Contest 318

Full Moon

模拟。

1
2
3
4
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), p = io.nextInt();
    io.println(n < m ? 0 : (n - m) / p + 1);
}

Overlapping sheets

比赛时没什么思路，想到扫描线，就用扫描线 + 区间合并来做了。结果一看题解，暴力标记每个点，没想到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), ans = 0;
    int[][] g = new int[100][100];
    for (int i = 0; i < n; i++) {
        int a = io.nextInt(), b = io.nextInt();
        int c = io.nextInt(), d = io.nextInt();
        for (int x = a; x < b; x++) {
            for (int y = c; y < d; y++) {
                if (g[x][y]++ == 0) ans++;
            }
        }
    }
    io.println(ans);
}

Blue Spring

看到大佬的解法后，感觉我模拟的方式好蠢啊。当时我是枚举是否要买 \(d\) 张票，有点麻烦，原来枚举买当日的票更简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt(), d = io.nextInt(), p = io.nextInt();
    int[] f = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        f[i] = io.nextInt();
    }
    Arrays.sort(f);
    long ans = Long.MAX_VALUE, sum = 0L;
    for (int i = 0; i <= n; i++) {
        sum += f[i];
        ans = Math.min(ans, sum + (long) (n - i + d - 1) / d * p);
    }
    io.println(ans);
}

General Weighted Max Matching

动态规划有点不太会，赛时瞎搞 AC 的。记忆化搜索会很好写，然后 DP 的话，我是用三层循环解决的，下面的解法优化掉一层循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void solve() {
    int n = io.nextInt();
    int[][] d = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            d[i][j] = io.nextInt();
        }
    }
    long[] dp = new long[1 << n];
    for (int k = 2; k < 1 << n; k++) {
        int i = Integer.numberOfTrailingZeros(k & -k);
        dp[k] = dp[k ^ (1 << i)];
        for (int j = i + 1; j < n; j++) {
            if ((k >> j & 1) == 1) {
                dp[k] = Math.max(dp[k], dp[k ^ (1 << i) ^ (1 << j)] + d[i][j]);
            }
        }
    }
    io.println(dp[(1 << n) - 1]);
}

Sandwiches

比较显然的做法是把相同的数分为一组，然后组内枚举中间的数。对于每个中间的数，让答案加上 \(L\times R\)，其中 \(L\) 和 \(R\) 分别是左右两边相等的数的个数，枚举时可以一次性枚举间隔内所有数。

第二个解法是参考大佬的代码得到的，相当于枚举右端点吧。对于每个右端点，它的贡献可以根据下面代码中的公式得出，感觉比较巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solve() {
    int n = io.nextInt();
    int[] cnt = new int[n];
    long[] sum = new long[n];
    long ans = 0L;
    for (int i = 0; i < n; i++) {
        int a = io.nextInt() - 1;
        ans += (long) i * cnt[a] - sum[a] - (long) (1 + cnt[a]) * cnt[a] / 2;
        cnt[a]++;
        sum[a] += i;
    }
    io.println(ans);
}

Octopus

有点抽象，不是很懂。大概是枚举了 \(N^{2}\) 个极限位置，然后分别对每个位置判断可行性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public static void solve() {
    int N = io.nextInt();
    long[] X = new long[N];
    long[] L = new long[N];
    for (int i = 0; i < N; i++) {
        X[i] = io.nextLong();
    }
    for (int i = 0; i < N; i++) {
        L[i] = io.nextLong();
    }

    List<Long> pos = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            pos.add(X[i] - L[j]);
            pos.add(X[i] + L[j] + 1);
        }
    }
    Collections.sort(pos);

    long ans = 0L;
    for (int i = 0; i < pos.size() - 1; i++) {
        long[] dis = new long[N];
        for (int j = 0; j < N; j++) {
            dis[j] = Math.abs(pos.get(i) - X[j]);
        }
        Arrays.sort(dis);
        boolean ok = true;
        for (int j = 0; j < N; j++) {
            if (dis[j] > L[j]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ans += pos.get(i + 1) - pos.get(i);
        }
    }
    io.println(ans);
}
发表更新算法 / AtCoder5 分钟读完 (大约707个字)

AtCoder Beginner Contest 317

Potions

二分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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.

求和公式。

1
2
3
4
5
6
7
8
9
10
11
12
13
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 背包，比赛时转移方程弄错了一个细节，本来以为和答案是等价的，赛后改下就过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
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]);
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×