发表更新算法 / 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();
}
发表更新算法 / 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]);
    }
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×