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

Educational Codeforces Round 155 (Rated for Div. 2)

Rigged!

模拟。

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[] s = new int[n];
    int[] e = new int[n];
    for (int i = 0; i < n; i++) {
        s[i] = io.nextInt();
        e[i] = io.nextInt();
    }
    for (int i = 1; i < n; i++) {
        if (s[i] >= s[0] && e[i] >= e[0]) {
            io.println(-1);
            return;
        }
    }
    io.println(s[0]);
}

Chips on the Board

有两种情况，每行都放一个或者每列都放一个，然后模拟即可。

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[] a = new int[n];
    int[] b = new int[n];
    long suma = 0L;
    int mina = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        suma += a[i];
        mina = Math.min(mina, a[i]);
    }
    long sumb = 0L;
    int minb = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
        sumb += b[i];
        minb = Math.min(minb, b[i]);
    }
    io.println(Math.min(suma + (long) minb * n, sumb + (long) mina * n));
}

Make it Alternating

所有连续重复数的个数就是最少操作次数，然后就是简单的应用组合数学。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static final int MOD = 998244353;

public static void solve() {
    char[] s = io.next().toCharArray();
    int n = s.length;
    long cnt = n, sum = 1L;
    for (int i = 0; i < n; ) {
        int j = i + 1;
        while (j < n && s[j] == s[j - 1]) {
            j++;
        }
        sum = sum * (j - i) % MOD;
        cnt--;
        i = j;
    }
    for (long i = 1; i <= cnt; i++) {
        sum = sum * i % MOD;
    }
    io.println(cnt + " " + sum);
}

Sum of XOR Functions

固定右端点，然后分别考虑每一位，计算答案，公式如下：

$$ \sum_{r=1}^{n}\sum_{l=1}^{r}f(l,r)\cdot (r-l+1) =\sum_{r=1}^{n}\sum_{i=0}^{31}\sum_{l=1}^{r}(f_{i}(1,r)\oplus f_{i}(1,l-1))\cdot (r-(l-1)) $$

可以发现对于每一位，\(f_{i}(1,r)\oplus f_{i}(1,l-1)\) 的值不是 \(1\) 就是 \(0\)，只有当值为 \(1\) 时才会对答案有贡献。如果 \(f_{i}(1,r)=1\)，那么右端点 \(r\) 的第 \(i\) 位对答案的贡献为 \((cnt[i][0]\cdot r-sum[i][0])\cdot 2^{i}\)（其中 \(cnt[i][0]\) 表示前缀中 \(f_{i}=0\) 的个数，\(sum[i][0]\) 表示前缀中 \(f_{i}=0\) 的区间长度之和），另一种情况同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private static final int MOD = 998244353;

public static void solve() {
    int n = io.nextInt();
    int[] s = new int[n + 1];
    for (int i = 0; i < n; i++) {
        s[i + 1] = s[i] ^ io.nextInt();
    }

    long ans = 0L;
    long[][] cnt = new long[32][2];
    long[][] sum = new long[32][2];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 32; j++) {
            int x = s[i] >> j & 1;
            ans = (ans + (cnt[j][x ^ 1] * i - sum[j][x ^ 1]) % MOD * (1 << j)) % MOD;
            cnt[j][x]++;
            sum[j][x] += i;
        }
    }
    io.println(ans);
}
发表更新算法 / Codeforces4 分钟读完 (大约595个字)

Codeforces Round 899 (Div. 2)

Increasing Sequence

模拟，注意最后答案要减一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }

    int b = 1;
    for (int i = 0; i < n; i++) {
        if (b == a[i]) b += 2;
        else b += 1;
    }
    io.println(b - 1);
}

Sets and Union

比赛时写复杂了，就是枚举不选哪个数，使用位运算会很简单。

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
public static void solve() {
    int n = io.nextInt();

    long xor = 0L;
    long[] s = new long[n];
    for (int i = 0; i < n; i++) {
        int k = io.nextInt();
        for (int j = 0; j < k; j++) {
            s[i] |= 1L << io.nextInt();
        }
        xor |= s[i];
    }

    int ans = 0;
    for (int i = 1; i <= 50; i++) {
        if ((xor >> i & 1) != 1) continue;
        long res = 0L;
        for (int j = 0; j < n; j++) {
            if ((s[j] >> i & 1) != 1) {
                res |= s[j];
            }
        }
        ans = Math.max(ans, Long.bitCount(res));
    }
    io.println(ans);
}

Card Game

思维题，没想出来。不管前两张牌如何操作，都必定可以拿到之后的所有正数牌，然后对前两张牌分类讨论即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    long ans = 0L;
    for (int i = 2; i < n; i++) {
        ans += Math.max(0, a[i]);
    }
    ans += Math.max(0, a[0] + Math.max(0, n > 1 ? a[1] : 0));
    io.println(ans);
}

Tree XOR

很典的换根 DP，因为第三题花费太长时间，导致差几分钟 AC。只要相邻的两个节点值不相同，它们就需要做一次操作。先以一个节点为根做 DFS，并记录所有节点的子树大小，和以该节点为根的成本。然后再做一次 DFS，换根计算代价的差值。（比赛时犯蠢，在换根的过程中打印答案，但是遍历不能保证从 \(1\) 到 \(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
39
40
41
42
43
44
private static long[] ans;
private static int[] value, sz;
private static List<Integer>[] g;

public static void solve() {
    int n = io.nextInt();
    value = new int[n];
    for (int i = 0; i < n; i++) {
        value[i] = io.nextInt();
    }
    g = new List[n];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < n - 1; i++) {
        int u = io.nextInt() - 1, v = io.nextInt() - 1;
        g[u].add(v);
        g[v].add(u);
    }
    sz = new int[n];
    ans = new long[n];
    dfs1(0, -1);
    dfs2(0, -1);
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

private static void dfs1(int x, int fa) {
    sz[x] = 1;
    for (int y : g[x]) {
        if (y == fa) continue;
        dfs1(y, x);
        sz[x] += sz[y];
        ans[0] += (long) sz[y] * (value[x] ^ value[y]);
    }
}

private static void dfs2(int x, int fa) {
    for (int y : g[x]) {
        if (y == fa) continue;
        ans[y] = ans[x] + (long) (sz[0] - sz[y] - sz[y]) * (value[x] ^ value[y]);
        dfs2(y, x);
    }
}
发表更新算法 / 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();
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×