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

Educational Codeforces Round 157 (Rated for Div. 2)

Treasure Chest

至少走 \(\max(x,y)\) 步，因为最多能扛起箱子 \(k\) 秒，所以会往回走 \(\max(0,y-x-k)\) 步。

1
2
3
4
public static void solve() {
    int x = io.nextInt(), y = io.nextInt(), k = io.nextInt();
    io.println(Math.max(x, y) + Math.max(0, y - x - k));
}

Points and Minimum Distance

排序，然后将数组分为左右两部分，分别代表 \(x,y\) 坐标序列。可以证明，这是最优的。

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[2 * n];
    for (int i = 0; i < 2 * n; i++) {
        a[i] = io.nextInt();
    }
    Arrays.sort(a);

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

Torn Lucky Ticket

对于每个字符串 \(s_{i}\)，我们枚举合并字符串的中心位置，这样就可以知道需要在前缀或后缀补上长度以及总和为多少的字符串，使得合并字符串为幸运的。因为合并字符串的中心位置可能不在当前字符串上，所以我们按照长度从小到大处理字符串，这样可以保证不漏掉任何情况。特别的，每个字符串都可以和自身连接成为幸运串。或者也可以进行预处理，这样就不用排序。

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
public static void solve() {
    int n = io.nextInt();
    char[][] arr = new char[n][];
    for (int i = 0; i < n; i++) {
        arr[i] = io.next().toCharArray();
    }
    Arrays.sort(arr, (s1, s2) -> s1.length - s2.length);

    long ans = 0L;
    int[][] dp = new int[6][46];
    for (char[] s : arr) {
        int m = s.length;
        int[] sum = new int[m + 1];
        for (int j = 0; j < m; j++) {
            sum[j + 1] =  sum[j] + s[j] - '0';
        }

        for (int j = m / 2 + 1; j <= m; j++) {
            ans += dp[2 * j - m][Math.max(0, 2 * sum[j] - sum[m])];
            ans += dp[2 * j - m][Math.max(0, sum[m] - 2 * sum[m - j])];
        }
        dp[m][sum[m]]++;
    }
    io.println(ans + n);
}

XOR Construction

首先构造满足第二个条件的数组 \(b\)，我们让 \(b_{n}=0\)，然后前面的每个元素 \(b_{i}=a_{i}\oplus a_{i+1}\oplus\cdots\oplus a_{n-1}\)，这样就得到满足第二个条件的数组，可以通过后缀异或得到。那么如何让 \(b\) 包含从 \(0\) 到 \(n-1\) 的每个数，因为数据保证总是可以构造出这样的序列，也就是说我们得到的数组 \(b\) 异或某个数，就能够得到目标数组。单独考虑每一位是否需要异或，可以发现，如果该位 \(1\) 的数量大于 \(0\) 的数量就需要进行异或操作。

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

    for (int i = n - 2; i >= 0; i--) {
        a[i] = a[i] ^ a[i + 1];
    }

    int[] d = new int[30];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 30; j++) {
            d[j] += a[i] >> j & 1;
        }
    }

    int mask = 0;
    for (int i = 0; i < 30; i++) {
        if (d[i] > n - d[i]) {
            mask |= 1 << i;
        }
    }

    for (int i = 0; i < n; i++) {
        io.print((a[i] ^ mask) + " ");
    }
    io.println();
}
发表更新算法 / Codeforces9 分钟读完 (大约1380个字)

Codeforces Round 907 (Div. 2)

Sorting with Twos

因为每次只能操作区间 \([1,2^{m}]\)，所以 \([2^{m}+1,2^{m+1}]\) 内的所有数是同时进行操作的，它们需要满足非递减的性质，最后不要忘记结尾不能操作的数也需要满足条件。

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 + 1];
    for (int i = 1; i <= n; i++) {
        a[i] = io.nextInt();
    }

    for (int i = 1; 1 << i <= n; i++) {
        int j = Math.min(1 << (i + 1), n);
        for (int k = (1 << i) + 1; k < j; k++) {
            if (a[k] > a[k + 1]) {
                io.println("NO");
                return;
            }
        }
    }
    io.println("YES");
}

Deja Vu

如果一个数能够被 \(2^{i}\) 整除，那么操作之后，它只能被所有小于等于 \(2^{i-1}\) 的二的幂整除。所以预处理所有修改，只保留满足递减顺序的修改，然后模拟即可。或者也可以直接修改，不用预处理，在修改之前判断一下是否比上次小就行。

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

    int mask = 0;
    for (int i = 0; i < q; i++) {
        int x = io.nextInt();
        if (mask == 0 || (1 << x) <= (mask & -mask)) {
            mask |= 1 << x;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 30; j >= 0; j--) {
            if ((mask >> j & 1) == 1 && a[i] % (1 << j) == 0) {
            	a[i] += 1 << (j - 1);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        io.print(a[i] + " ");
    }
    io.println();
}

Smilo and Monsters

比赛时我是排序 + 相向双指针模拟的，先干前面的怪物，如果计数和最后一个的怪物群数量相等，则使用终极攻击，比较麻烦的是双指针到达同一个位置时，需要特判一些情况。然后下面的解法，很简洁啊。似乎总是可以使用普通攻击干掉怪物总数的一半向上取整，并且使用终极攻击干掉总数的一半向下取整。然后排序数组并倒序遍历，使得一次终极攻击干掉尽可能多的怪物，这样就得到最少攻击次数。

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

Suspicious logarithms

\(f(x)\) 表示 \(x\) 的二进制表示中最高位的 \(1\) 所在的位数 \(y\)，而 \(g(x)\) 表示满足 \(y^{z}<= x\) 条件的最大的 \(z\)。可以发现如果 \(y=2,x=10^{18}\)，则 \(z=59\)。我们可以枚举所有 \(y\in[2,59]\)，对于特定的 \(y\)，枚举不同的 \(z\) 覆盖的区间范围。得到各个区间范围内所有数的 \(z\) 值，我们就可以在 \(O(\log{(r-l+1)})\) 的时间复杂度内执行查询。为了避免乘法溢出，在进行比较时需要使用除法。其他人代码有直接使用 \(\log\) 的，也比较简单啊，我还以为很麻烦，结果溢出没想到换除法。当然也可以维护前缀和，然后二分区间位置来进行查询。

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
private static final int MOD = (int) 1e9 + 7;
private static final List<long[]>[] list = new List[60];

static {
    Arrays.setAll(list, k -> new ArrayList<>());

    for (int f = 2; f < 60; f++) {
        long l = 1L << f, r = (1L << f + 1) - 1;

        long k = f, g = 1;
        while (k <= l / f) {
            k *= f;
            g++;
        }

        for (; l <= r; l = k + 1, g++) {
            k = k <= r / f ? k * f - 1 : r;
            list[f].add(new long[]{l, k, g});
        }
    }
}

public static void solve() {
    long ans = 0L;
    long l = io.nextLong(), r = io.nextLong();
    int i = 63 - Long.numberOfLeadingZeros(l);
    int j = 63 - Long.numberOfLeadingZeros(r);
    for (; i <= j; i++) {
        for (long[] t : list[i]) {
            ans = (ans + (Math.max(0, Math.min(t[1], r) - Math.max(t[0], l) + 1)) * t[2]) % MOD;
        }
    }
    io.println(ans);
}

A Growing Tree

每个节点的编号是添加该节点时树的大小，因为修改操作不会影响还未添加到树上的节点，所以我们对每个修改操作添加一个编号（时间），表示修改所影响的范围。我们可以使用单点修改、区间查询的树状数组维护修改操作的编号，然后按照 DFS 序遍历树，每当遍历到一个节点，使用树状数组进行单点修改，因为遍历是 DFS 序，所以当前节点的祖先节点已经进行过修改操作，那么当前节点的答案就是所有大于等于该节点编号的修改操作之和。

那么有没有可能该答案会包含其他满足编号大于当前节点的非祖先节点的修改操作呢，不会包含，因为遍历是 DFS 序，DFS 返回时会取消对节点的修改操作，所以每当遍历到一个节点，修改操作只会包含其祖先节点的修改操作。特别注意，数组开 \(q+2\) 的大小，因为初始时有一个根节点，所以节点数量最多为 \(q+1\)，然后编号从 \(1\) 开始。

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
public static void solve() {
    int q = io.nextInt(), sz = 1;
    List<int[]>[] queries = new List[q + 2];
    Arrays.setAll(queries, k -> new ArrayList<>());
    List<Integer>[] g = new List[q + 2];
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int i = 0; i < q; i++) {
        int t = io.nextInt();
        if (t == 1) {
            int v = io.nextInt();
            g[v].add(++sz);
        } else {
            int v = io.nextInt(), x = io.nextInt();
            queries[v].add(new int[]{sz, x});
        }
    }
    var bit = new BIT(sz);
    long[] ans = new long[sz + 1];
    dfs(1, sz, g, queries, bit, ans);
    for (int i = 1; i <= sz; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

private static void dfs(int x, int sz, List<Integer>[] g, List<int[]>[] queries, BIT bit, long[] ans) {
    for (int[] q : queries[x]) {
        bit.add(q[0], q[1]);
    }
    ans[x] = bit.get(x, sz);
    for (int y : g[x]) {
        dfs(y, sz, g, queries, bit, ans);
    }
    for (int[] q : queries[x]) {
        bit.add(q[0], -q[1]);
    }
}
发表更新算法 / Codeforces6 分钟读完 (大约898个字)

Codeforces Round 905 (Div. 2)

Chemistry

只要奇数字母的个数不大于 \(k+1\) 即可，因为回文串最多有一个奇数字母。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    String s = io.next();

    int[] cnt = new int[26];
    for (int i = 0; i < n; i++) {
        cnt[s.charAt(i) - 'a']++;
    }

    int sum = 0;
    for (int x : cnt) {
        if (x % 2 == 1) {
            sum++;
        }
    }
    io.println(sum - 1 > k ? "NO" : "YES");
}

Raspberries

当 \(k=2,3,5\) 时，因为 \(k\) 是质数，如果所有数的乘积能够被 \(k\) 整除，必定存在一个数能够被 \(k\) 整除，所以单独计算每个数即可。当 \(k=4\) 时，需要计算存在一个数能被 \(4\) 整除的最少操作数，还需要计算存在两个能被 \(2\) 整除的数的最少操作数，答案为两者的最小值。

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();

    int cnt = 0;
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
        if (a[i] % 2 == 0) {
            cnt++;
        }
    }

    int ans = k;
    for (int i = 0; i < n; i++) {
        ans = Math.min(ans, (k - a[i] % k) % k);
    }
    if (k == 4) {
        ans = Math.min(ans, Math.max(0, 2 - cnt));
    }
    io.println(ans);
}

You Are So Beautiful

如果某个子数组作为子序列只出现过一次，因为子数组本身就是子序列，所以没有其他方式能够构成该子数组，即子数组的左端点左边没有和它相同的数，右端点的右边也没有和它相同的数。我们可以使用集合 + 前缀和的方式预先计算每个位置及其左边满足条件的左端点个数，然后倒序处理数组，对每个满足条件的右端点，都将其对应的左端点的个数添加到答案。

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 n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }

    Set<Integer> set = new HashSet<>();
    int[] prefix = new int[n + 1];
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + (set.add(a[i]) ? 1 : 0);
    }
    set.clear();

    long ans = 0L;
    for (int i = n - 1; i >= 0; i--) {
        if (set.add(a[i])) {
            ans += prefix[i + 1];
        }
    }
    io.println(ans);
}

Dances (Easy version)

题目真难读，简单版只会在数组 \(a\) 中添加一个 \(1\)，然后计算最少操作数，可以使用排序 + 双指针进行处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    a[0] = 1;
    for (int i = 1; i < n; i++) {
        a[i] = io.nextInt();
    }
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
        b[i] = io.nextInt();
    }

    Arrays.sort(a);
    Arrays.sort(b);

    int k = 0;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            k++;
            j++;
        }
    }
    io.println(k);
}

Dances (Hard Version)

困难版，计算在数组中分别添加 \([1,m]\) 需要的最少操作数。通过观察可以发现（真发现不了），改变 \(a[0]\) 最多只会使操作次数加 \(1\)，所以我们可以二分该边界值，然后计算答案即可。

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

    int k = calc(a, b, 1);

    int lo = 1, hi = m;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (calc(a, b, mid) == k) lo = mid + 1;
        else hi = mid - 1;
    }
    io.println((long) m * k + (m - lo + 1));
}

private static int calc(int[] a, int[] b, int x) {
    a[0] = x;
    a = a.clone();
    Arrays.sort(a);

    int n = a.length, k = 0;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            k++;
            j++;
        }
    }
    return k;
}

竟然还有更简单的方法，首先计算 \(a\) 中 \(n-1\) 个数对应 \(b\) 中 \(n\) 个数的最少删除次数，并同时维护 \(b\) 中不满足 \(a[i]<b[j]\) 的最后一个值，该值就是操作次数的分界点，直接计算答案即可。

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

    Arrays.sort(a);
    Arrays.sort(b);

    int k = 0, val = m + 1;
    for (int i = 0, j = 0; i < n - k; i++, j++) {
        while (j < n && a[i] >= b[j]) {
            val = b[j];
            k++;
            j++;
        }
    }
    io.println((long) m * (k - 1) + Math.max(0, m - val + 1));
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×