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

Codeforces Round 908 (Div. 2)

Secret Sport

因为题目保证存在合法的 \(X\) 和 \(Y\)，那么获胜者总是最后一个下棋者，因为如果不是最后一个，那么对局就不会结束。

1
2
3
4
5
public static void solve() {
    int n = io.nextInt();
    String s = io.next();
    io.println(s.charAt(n - 1));
}

Two Out of Three

对于一组相同元素，它只能满足一个条件，如果满足两个条件，那么它必定会满足三个条件。所以至少要有两组出现次数大于等于 \(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
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 k = 2;
    int[] b = new int[n];
    Arrays.fill(b, 1);
    int[] cnt = new int[101];
    for (int i = 0; i < n && k <= 3; i++) {
        if (++cnt[a[i]] == 2) {
            b[i] = k++;
        }
    }

    if (k <= 3) {
        io.println(-1);
        return;
    }
    for (int i = 0; i < n; i++) {
        io.print(b[i] + " ");
    }
    io.println();
}

Anonymous Informant

如果当前数组是通过移动得到，那么它的最后一个元素必定是由定点元素转移过来，所以我们只需要判断最后一个元素是否在 \([1,n]\) 范围内，然后不断地回滚左移操作，即不断地找到移动之前的最后一个元素位置，并进行判断即可。

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

    int i = n - 1;
    while (b[i] != -1 && b[i] < n && --k > 0) {
        int j = (i - (b[i] + 1) + n) % n;
        b[i] = -1;
        i = j;
    }
    io.println(k == 0 || b[i] == -1 ? "Yes" : "No");
}

Neutral Tonality

我们总是可以构造一个数组 \(c\)，使得 \(\operatorname{LIS}(c)=\operatorname{LIS}(a)\)，方法为将数组 \(b\) 中的元素 \(b_{i}\)，插入到数组 \(a\) 中第一个满足 \(a_{j}\leq b_{i}\) 的元素 \(a_{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
26
27
28
29
30
31
public static void solve() {
    int n = io.nextInt(), m = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt();
    }
    var b = new Integer[m];
    for (int i = 0; i < m; i++) {
        b[i] = io.nextInt();
    }
    Arrays.sort(b, ((e1, e2) -> e2 - e1));

    int i = 0, j = 0, k = 0;
    int[] ans = new int[n + m];
    while (i < n || j < m) {
        if (i >= n) {
            ans[k++] = b[j++];
        } else if (j >= m) {
            ans[k++] = a[i++];
        } else if (a[i] <= b[j]) {
            ans[k++] = b[j++];
        } else {
            ans[k++] = a[i++];
        }
    }

    for (int x : ans) {
        io.print(x + " ");
    }
    io.println();
}
发表更新算法 / LeetCode5 分钟读完 (大约709个字)

第 370 场力扣周赛

找到冠军 I

如果某一列全为 \(0\)，则该列表示的队伍会成为冠军。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        for (int j = 0; j < n; j++) {
            int cnt = 0;
            for (int i = 0; i < n && cnt == 0; i++) {
                cnt += grid[i][j];
            }
            if (cnt == 0) {
                return j;
            }
        }
        return -1;
    }
}

找到冠军 II

相当于判断入度为 \(0\) 的节点是否只有一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findChampion(int n, int[][] edges) {
        int[] in = new int[n];
        for (var e : edges) {
            in[e[1]]++;
        }
        int ans = -1;
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                if (ans == -1) ans = i;
                else return -1;
            }
        }
        return ans;
    }
}

在树上执行操作以后得到的最大分数

树形 DP，要求最大分数，可以先求损失的最小分数，然后使用总分减去该分数即可。

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
class Solution {
    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        long ans = 0L;
        for (int x : values) {
            ans += x;
        }
        return ans - dfs(0, -1, g, values);
    }
    
    private long dfs(int x, int fa, List<Integer>[] g, int[] values) {
        if (g[x].size() == 1 && g[x].get(0) == fa) {
            return values[x];
        }
        long res = 0L;
        for (int y : g[x]) {
            if (y != fa) {
                res += dfs(y, x, g, values);
            }
        }
        return Math.min(res, values[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
class Solution {
    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        int n = values.length;
        List<Integer>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : edges) {
            int u = e[0], v = e[1];
            g[u].add(v);
            g[v].add(u);
        }
        long[] sum = new long[n];
        return dfs(0, -1, g, values, sum);
    }
    
    private long dfs(int x, int fa, List<Integer>[] g, int[] values, long[] sum) {
        sum[x] = values[x];
        if (g[x].size() == 1 && g[x].get(0) == fa) {
            return 0;
        }
        long dp0 = values[x], dp1 = 0;
        for (int y : g[x]) {
            if (y != fa) {
                dp0 += dfs(y, x, g, values, sum);
                dp1 += sum[y];
            }
        }
        sum[x] += dp1;
        return Math.max(dp0, dp1);
    }
}

平衡子序列的最大和

离散化 + 树状数组优化 DP，直接看灵神代码吧。

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
// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/maximum-balanced-subsequence-sum/solutions/2513121/shu-zhuang-shu-zu-you-hua-dp-by-endlessc-3zf4/
class Solution {
    public long maxBalancedSubsequenceSum(int[] nums) {
        int n = nums.length;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = nums[i] - i;
        }
        Arrays.sort(b);
 
        BIT t = new BIT(b.length + 1);
        for (int i = 0; i < n; i++) {
            // j 为 nums[i]-i 离散化后的值（从 1 开始）
            int j = Arrays.binarySearch(b, nums[i] - i) + 1;
            long f = Math.max(t.preMax(j), 0) + nums[i];
            t.update(j, f);
        }
        return t.preMax(b.length);
    }
}

// 树状数组模板（维护前缀最大值）
class BIT {
    private long[] tree;

    public BIT(int n) {
        tree = new long[n];
        Arrays.fill(tree, Long.MIN_VALUE);
    }

    public void update(int i, long val) {
        while (i < tree.length) {
            tree[i] = Math.max(tree[i], val);
            i += i & -i;
        }
    }

    public long preMax(int i) {
        long res = Long.MIN_VALUE;
        while (i > 0) {
            res = Math.max(res, tree[i]);
            i &= i - 1;
        }
        return res;
    }
}
发表更新算法 / 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();
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×