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

Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)

Increasing and Decreasing

比赛时漏看第三个条件，搞半天。而且似乎倒着减会比较容易做（差不多）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int x = io.nextInt(), y = io.nextInt(), n = io.nextInt();
    int z = (1 + n - 1) * (n - 1) / 2;
    if (z > y - x) {
        io.println(-1);
        return;
    }
    io.print(x + " ");
    int d = x + y - x - z;
    for (int i = n - 1; i >= 1; i--) {
        d += i;
        io.print(d + " ");
    }
    io.println();
}

Swap and Reverse

找规律。第一个操作表明奇数下标相互连通，偶数下标相互连通。第二个操作，如果 \(k\) 是奇数，则连通性不会改变，分别对奇偶字母排序，然后构造即可；如果 \(k\) 是偶数，则奇数下标和偶数下标相互连通，对所有字母排序即可。

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(), k = io.nextInt();
    char[] s = io.next().toCharArray();
    if (k % 2 == 0) {
        Arrays.sort(s);
        io.println(new String(s));
    } else {
        PriorityQueue<Character> list1 = new PriorityQueue<>();
        PriorityQueue<Character> list2 = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) list1.add(s[i]);
            else list2.add(s[i]);
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) sb.append(list1.poll());
            else sb.append(list2.poll());
        }
        io.println(sb.toString());
    }
}

Divisor Chain

比赛时瞎猜 AC 的，当时是想从 \(1\) 开始构造到 \(x\)，过程比答案复杂。正解是从 \(x\) 一直减去最低有效位的一（必定是除数），直到 \(x\) 等于 \(2\) 的幂（只剩一个一），然后让 \(x\) 一直减去 \(\frac{x}{2}\) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void solve() {
    int x = io.nextInt();
    List<Integer> ans = new ArrayList<>();
    ans.add(x);
    while ((x & (x - 1)) != 0) {
        x &= (x - 1);
        ans.add(x);
    }
    while (x != 1) {
        x /= 2;
        ans.add(x);
    }
    io.println(ans.size());
    for (int y : ans) {
        io.print(y + " ");
    }
    io.println();
}

Matrix Cascade

使用差分数组维护从上到下的翻转次数，需要注意的是正负需要分开存，正数每层左移一位，负数每层右移一位。PS：这题 \(p\) 和 \(q\) 总是写错，Debug 很久。以及大佬的代码看不懂。

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
public static void solve() {
    int n = io.nextInt();
    char[][] a = new char[n][];
    for (int i = 0; i < n; i++) {
        a[i] = io.next().toCharArray();
    }
    int ans = 0;
    int[] p = new int[n + 1];
    int[] q = new int[n + 1];
    int[] sum = new int[n + 1];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] - '0' != sum[j + 1] % 2) {
                ans++;
                p[j] ^= 1;
                q[j + 1] ^= 1;
            }
        }
        p[0] ^= p[1];
        for (int j = 1; j < n; j++) {
            p[j] = p[j + 1];
        }
        q[n] ^= q[n - 1];
        for (int j = n - 1; j > 0; j--) {
            q[j] = q[j - 1];
        }
        for (int j = 0; j < n; j++) {
            sum[j + 1] = sum[j] ^ p[j] ^ q[j];
        }
    }
    io.println(ans);
}

Guess Game

有点难以描述，超出能力范围了。这是一个比较好理解的做法，分别考虑每一位。从最低位开始，如果前缀相同，那么就计算当前位 \(0\) 和 \(1\) 的个数，只有爱丽丝拿 \(1\)，鲍勃拿 \(1\) 或 \(0\) 的情况，当前位才会多走一轮。初始时，设置答案为 \(n \times n\)，因为每个组合至少会走一轮。最后需要使用快速幂求 \(n\) 的逆元。

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
private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    Arrays.sort(a);
    long ans = (long) n * n;
    for (int t = 0; t < 30; t++) {
        for (int l = 0, r = 0; l < n; l = r) {
            int[] cnt = new int[2];
            while (r < n && a[l] / 2 == a[r] / 2) {
                cnt[a[r] % 2]++;
                r++;
            }
            ans += (long) cnt[1] * (cnt[1] + cnt[0]);
        }
        for (int i = 0; i < n; i++) {
            a[i] /= 2;
        }
    }
    ans = ans % MOD * pow(n, MOD - 2) % MOD * pow(n, MOD - 2) % MOD;
    io.println(ans);
}

private static int pow(int a, int n) {
    long res = 1, x = a;
    while (n != 0) {
        if (n % 2 == 1) {
            res = (res * x) % MOD;
        }
        x = (x * x) % MOD;
        n >>= 1;
    }
    return (int) res;
}
发表更新算法 / Codeforces7 分钟读完 (大约1103个字)

Codeforces Round 894 (Div. 3)

Gift Carpet

从左到右每列贪心取即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void solve() {
    int m = io.nextInt(), n = io.nextInt();
    String[] g = new String[m];
    for (int i = 0; i < m; i++) {
        g[i] = io.next();
    }
    int idx = 0;
    String s = "vika";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[j].charAt(i) == s.charAt(idx)) {
                idx++;
                break;
            }
        }
        if (idx == s.length()) {
            io.println("YES");
            return;
        }
    }
    io.println("NO");
}

Sequence Game

构造题。当 \(b_{i-1}>b_{i}\) 时，在两个数中间添加一个 \(1\) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void solve() {
    int n = io.nextInt();
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }
    List<Integer> ans = new ArrayList<>();
    ans.add(b[0]);
    for (int i = 1; i < n; i++) {
        if (b[i] < b[i - 1]) ans.add(1);
        ans.add(b[i]);
    }
    io.println(ans.size());
    for (int x : ans) io.print(x + " ");
    io.println();
}

Flower City Fence

阅读理解。题目中的“对角线对称”这个概念根本不用管，就是不断对区间做加法，然后判断是否和原数组相等，可以使用差分 + 前缀和解决。看完题解，发现其实也可以 \(O(1)\) 空间解决，因为数组是非递增的，按顺序遍历就行，具体见代码。

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

Ice Cream Balls

题目描述很有问题，其实就是问从一个长度为 \(m\) 的序列中选两个值组成集合，使得不同集合的数目恰好为 \(n\) 的 \(m\) 是多少。可以先二分求 \(x\)，使得 \(C_{x}^{2}\leq n\) 且 \(C_{x+1}^{2}>n\)。然后答案就是 \(x+(n-C_{x}^{2})\)，表示 \([1,n-C_{x}^{2}]\) 范围内的每个数各取两个，以及 \([n-C_{x}^{2}+1,x]\) 范围内的每个数各取一个。PS：读题很容易漏掉恰好两个字。

1
2
3
4
5
6
7
8
9
10
public static void solve() {
    long n = io.nextLong();
    long lo = 2, hi = (long) 1e9 * 2;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        if (mid * (mid - 1) / 2 <= n) lo = mid + 1;
        else hi = mid - 1;
    }
    io.println(hi + (n - hi * (hi - 1) / 2));
}

Kolya and Movie Theatre

做这道题时漏掉“开业前一天去过电影院”这个条件，导致想了半天。答案要求最多看 \(m\) 部电影的最大娱乐价值，首先我们可以观察到娱乐值的下降幅度只与最后一次去电影院的日期 \(x\) 有关，即下降幅度为 \(x\cdot d\)。所以我们可以从前往后枚举 \(x\)，并且维护最大长度为 \(m\) 的优先队列，来保证最多看 \(m\) 部电影。需要注意电影的娱乐值可能是负数，而我们只需要在优先队列中存储正数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), d = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) a[i] = io.nextInt();
    PriorityQueue<Integer> q = new PriorityQueue<>();
    long sum = 0L, ans = 0L;
    for (int i = 0; i < n; i++) {
        if (a[i] <= 0) continue;
        q.offer(a[i]);
        sum += a[i];
        if (q.size() > m) sum -= q.poll();
        ans = Math.max(ans, sum - (long) d * (i + 1));
    }
    io.println(ans);
}

Magic Will Save the World

初见时想到的是二分时间 + 动态规划，赛后优化发现可以直接动态规划做。我是用背包做的，\(dp[i][j]\) 表示前 \(i\) 个怪物使用 \(j\) 点法术值能够击败的怪物总强度最大是多少，然后枚举水法术值计算答案。但是其实可以不用这样，我们只需要知道怪物的子集的所有可能强度是多少，然后枚举所有能够到达的强度即可。（C++ 位图很方便）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void solve() {
    int w = io.nextInt(), f = io.nextInt(), n = io.nextInt();
    int sum = 0;
    int[] s = new int[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.nextInt();
        sum += s[i];
    }
    boolean[] dp = new boolean[sum + 1];
    dp[0] = true;
    for (int i = 0; i < n; i++) {
        for (int j = sum; j >= s[i]; j--) {
            dp[j] = dp[j] || dp[j - s[i]];
        }
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i <= sum; i++) {
        if (!dp[i]) continue;
        ans = Math.min(ans, Math.max((i + w - 1) / w, (sum - i + f - 1) / f));
    }
    io.println(ans);
}

The Great Equalizer

很容易就可以得出结论，设备的输出值是数组的最大值 + 排序后相邻元素的最大差值，但是不知道怎么维护。使用 C++ 的 multiset 很容易写，详细见大佬的代码。

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

Educational Codeforces Round 153 (Rated for Div. 2)

Not a Substring

构造题。如果 \(s\) 中存在连续相同的括号，则可以构造交替出现的括号；如果 \(s\) 是交替出现的括号，那么就构造连续的括号，此时包含的唯一交替的括号就是 \(()\)，特判一下即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    boolean ok = false;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            ok = true;
            break;
        }
    }
    if (new String(s).equals("()")) {
        io.println("NO");
        return;
    }
    io.println("YES");
    if (ok) io.println("()".repeat(n));
    else io.println("(".repeat(n) + ")".repeat(n));
}

Fancy Coins

数学题。假设最终使用 \(x\) 枚价值为 \(1\) 的硬币，\(y\) 枚价值为 \(k\) 的硬币。如果 \(x\) 大于等于 \(k\)，我们总是将其合成为价值为 \(k\) 的硬币，所以可以保证 \(x\) 小于 \(k\)。显然 \(x=m\bmod k\)，\(y=\frac{m}{k}\)。那么需要补充多少花色硬币呢？易知，需要补充 \(\max(0,x-a_{1})\) 个价值为 \(1\) 的花色硬币，和 \(\max (0,y-a_{k}-\max (0,\frac{a_{1}-x}{k}))\) 个价值为 \(k\) 的花色硬币。

1
2
3
4
5
public static void solve() {
    int m = io.nextInt(), k = io.nextInt(), a1 = io.nextInt(), ak = io.nextInt();
    int ans = Math.max(0, m % k - a1) + Math.max(0, m / k - ak - Math.max(0, a1 - m % k) / k);
    io.println(ans);
}

Game on Permutation

一开始的想法是，如果某个元素左边恰好只有一个小于它的元素，那么该位置就是胜位。然而暴力找每个位置左边比它小的元素个数的时间复杂度是 \(O(n^{2})\)，赛时就不知道怎么优化。其实我们可以知道，给定一个序列，胜位是固定不变的。所以可以考虑维护左边的最小元素（表示下一步是否可以下棋）和最小的胜位（如果大于最小胜位，则当前位必输），然后就可以很方便的模拟出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt();
    int[] p = new int[n];
    int ans = 0, min = n + 1, minWin = n + 1;
    for (int i = 0; i < n; i++) {
        p[i] = io.nextInt();
        if (min < p[i] && p[i] <= minWin) {
            ans++;
            minWin = Math.min(minWin, p[i]);
        }
        min = Math.min(min, p[i]);
    }
    io.println(ans);
}

Balanced String

不会不会。。o(╥﹏╥)o

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×