发表更新算法 / 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]);
    }
}
发表更新算法 / Codeforces5 分钟读完 (大约710个字)

Codeforces Round 897 (Div. 2)

green_gold_dog, array and permutation

让最小值减去最大值，就一定可以得到 \(n\) 个不同的差值。

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();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    var aux = new Integer[n];
    for (int i = 0; i < n; i++) {
        aux[i] = i;
    }
    Arrays.sort(aux, (i, j) -> a[i] - a[j]);
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        int t = aux[i];
        ans[t] = n - i;
    }
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

XOR Palindromes

算是简单的分类讨论，比赛时写的稀烂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void solve() {
    int n = io.nextInt(), cnt = 0;
    char[] s = io.next().toCharArray();
    for (int i = 0; i < n / 2; i++) {
        if (s[i] != s[n - i - 1]) {
            cnt++;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i <= n; i++) {
        if (i < cnt || i > n - cnt || (i - cnt) % 2 == 1 && n % 2 == 0) {
            sb.append('0');
        } else {
            sb.append('1');
        }
    }
    io.println(sb);
}

Salyg1n and the MEX Game

比赛调试一小时，疯狂超时，结果是限制太强的原因。（浪费时间。）

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[] s = new int[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.nextInt();
    }
    Arrays.sort(s);
    int x = n;
    for (int i = 0; i < n ; i++) {
        if (s[i] != i) {
            x = i;
            break;
        }
    }
    while (x != -1) {
        io.println(x);
        io.flush();
        x = io.nextInt();
    }
}

Cyclic Operations

做了一个多小时 AC，有点像之前做的内向基环树，该题每个点都有个出边，所以至少有一个环。首先要特判 \(k=1\) 的情况，该情况每个位置都必须自成一个环，即 \(a_{i}=i\)；其他情况所有环的长度都必须为 \(k\)，这样可以保证答案存在。

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
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt() - 1;
    }

    int[] in = new int[n];
    for (int i = 0; i < n; i++) {
        in[b[i]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (in[i] == 0) {
            q.offer(i);
        }
    }
    while (!q.isEmpty()) {
        int x = q.poll();
        if (--in[b[x]] == 0) {
            q.offer(b[x]);
        }
    }

    int cnt = 0;
    boolean[] vis = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (in[i] == 0 || vis[i]) continue;
        int len = 0;
        for ( ; !vis[i]; i = b[i]) {
            vis[i] = true;
            len++;
        }
        if (len != k) {
            io.println("NO");
            return;
        }
        cnt++;
    }
    if (k == 1 && cnt != n) {
        io.println("NO");
    } else {
        io.println("YES");
    }
}

Salyg1n and Array (simple version)

注意，\(n\) 和 \(k\) 都是偶数！手推的话可能可以做出来吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    int ans = 0, i;
    for (i = 1; i + k - 1 <= n; i += k) {
        io.println("? " + i);
        io.flush();
        ans ^= io.nextInt();
    }
    for (; i <= n; i++) {
        io.println("? " + (i - k + 1));
        io.flush();
        ans ^= io.nextInt();
    }
    io.println("! " + ans);
    io.flush();
}

Salyg1n and Array (hard version)

技巧性有点强，真想不到。就是如果多出一部分，可以通过两次异或算出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    int ans = 0, i;
    for (i = 1; i + k - 1 <= n; i += k) {
        io.println("? " + i);
        io.flush();
        ans ^= io.nextInt();
    }
    int t = n - i + 1;
    io.println("? " + (n - k + 1 - t / 2));
    io.flush();
    ans ^= io.nextInt();
    io.println("? " + (n - k + 1));
    io.flush();
    ans ^= io.nextInt();
    io.println("! " + ans);
    io.flush();
}
发表更新算法 / Codeforces8 分钟读完 (大约1146个字)

Codeforces Round 896 (Div. 2)

Make It Zero

挺简单的一道题，偶数长度的数组操作两次就可以，如果是奇数长度，则额外操作两次。写的时候，把 \(n\) 错写成 \(n-1\)，找 BUG 花了一倍的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    if (n % 2 == 0) {
        io.println(2);
        io.println(1 + " " + n);
        io.println(1 + " " + n);
        return;
    }
    io.println(4);
    io.println(1 + " " + (n - 1));
    io.println(1 + " " + (n - 1));
    io.println((n - 1) + " " + n);
    io.println((n - 1) + " " + n);
}

2D Traveling

\(a\) 和 \(b\) 的最短距离有两种情况，一个是 \(a\) 和 \(b\) 的曼哈顿距离，另一个是 \(a\) 和 \(b\) 经过 \(k\) 的曼哈顿距离，该情况只要求 \(k\) 个点中距离 \(a\) 和距离 \(b\) 最近的距离就行。比赛时遇到个坑点，两个 Long.MAX_VALUE 相加会溢出，所以初始时除以二。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt(), k = io.nextInt(), a = io.nextInt(), b = io.nextInt();
    long[] x = new long[n], y = new long[n];
    for (int i = 0; i < n; i++) {
        x[i] = io.nextInt();
        y[i] = io.nextInt();
    }
    long ak = Long.MAX_VALUE / 2, bk = Long.MAX_VALUE / 2;
    for (int i = 0; i < k; i++) {
        ak = Math.min(ak, Math.abs(x[i] - x[a - 1]) + Math.abs(y[i] - y[a - 1]));
        bk = Math.min(bk, Math.abs(x[i] - x[b - 1]) + Math.abs(y[i] - y[b - 1]));
    }
    long ab = Math.abs(x[b - 1] - x[a - 1]) + Math.abs(y[b - 1] - y[a - 1]);
    io.println(Math.min(ab, ak + bk));
}

Fill in the Matrix

比赛时代码很乱，赛后总是可以优化成比较简单的形式。分类讨论，\(n\) 和 \(m\) 的大小关系，可以直接得出最大美丽值，需要注意特判 \(m=1\) 的情况。然后就是构造，当 \(n\leq m-1\) 时，让一个从 \(0\) 开始的数组循环左移来构造行，这样可以保证得到最大美丽值；当 \(n>m-1\) 时，前 \(m-1\) 行与之前一样构造，之后多余的行只需要和最后一行相同即可（保证不会影响美丽值）。

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(), m = io.nextInt();
    if (m == 1) {
        io.println(0);
    } else if (n <= m - 1) {
        io.println(n + 1);
    } else {
        io.println(m);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i < Math.min(n, m - 1)) {
                io.print((j + i) % m + " ");
            } else {
                io.print(j + " ");
            }
        }
        io.println();
    }
}

Candy Party (Easy Version)

找 BUG 花了半个小时，将判断 hi 是否是二的幂写成 hi % 2 != 0，修改为 Long.bitCount(hi) != 1 后通过，也可以写成 (hi & hi - 1) != 0。因为每个人都需要发送和接收糖果，计算每个人和平均糖果数的差值 \(x\)，如果 \(x\) 的二进制位不是由连续的 \(1\) 组成，那么就无解，否则总是有唯一的 \(lo\) 和 \(hi\)（都是二的幂），使得 \(hi-lo=|x|\)。这样可以计算出每个人发送和接收多少糖果，如果最后相互抵消，则存在满足题目要求的交换方案。

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 sum = 0L;
    long[] a = new long[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        sum += a[i];
    }
    if (sum % n != 0) {
        io.println("NO");
        return;
    }
    long avg = sum / n;
    int[] cnt = new int[32];
    for (int i = 0; i < n; i++) {
        if (a[i] == avg) continue;
        long x = Math.abs(a[i] - avg);
        long lo = x & -x, hi = x + lo;
        if (Long.bitCount(hi) != 1) {
            io.println("NO");
            return;
        }
        int p = Long.numberOfTrailingZeros(lo);
        int q = Long.numberOfTrailingZeros(hi);
        if (a[i] > avg) {
            cnt[p]--;
            cnt[q]++;
        } else {
            cnt[q]--;
            cnt[p]++;
        }
    }
    for (int i = 0; i < 32; i++) {
        if (cnt[i] != 0) {
            io.println("NO");
            return;
        }
    }
    io.println("YES");
}

Candy Party (Hard Version)

考虑什么人可以不发送或者不接收糖果，必定是持有糖果数与平均糖果数的差值为二的幂的人，它们比原来多出一种选择，就是只执行一次发送或接收。具体操作见代码，有点说不清。最后大概是从高位到低位遍历，如果当前位不满足条件，就将低一位的差值与平均糖果数为二的幂的数分解。

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
public static void solve() {
    int n = io.nextInt();
    long sum = 0L;
    long[] a = new long[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        sum += a[i];
    }
    if (sum % n != 0) {
        io.println("NO");
        return;
    }
    long avg = sum / n;
    int[] cnt = new int[32];
    int[] in = new int[32], out = new int[32];
    for (int i = 0; i < n; i++) {
        if (a[i] == avg) continue;
        long x = Math.abs(a[i] - avg);
        if ((x & x - 1) == 0) {
            int r = Long.numberOfTrailingZeros(x);
            if (a[i] < avg) in[r]++;
            else out[r]++;
            continue;
        }
        long lo = x & -x, hi = x + lo;
        if ((hi & hi - 1) != 0) {
            io.println("NO");
            return;
        }
        int p = Long.numberOfTrailingZeros(lo);
        int q = Long.numberOfTrailingZeros(hi);
        if (a[i] > avg) {
            cnt[p]--;
            cnt[q]++;
        } else {
            cnt[q]--;
            cnt[p]++;
        }
    }
    for (int i = 31; i >= 0; i--) {
        cnt[i] += out[i] - in[i];
        if (i == 0) break;
        in[i - 1] -= cnt[i];
        out[i - 1] += cnt[i];
        if (in[i - 1] < 0 || out[i - 1] < 0) {
            io.println("NO");
            return;
        }
    }
    io.println(cnt[0] == 0 ? "YES" : "NO");
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×