Ligh0x74's Blog

2023-11-07发表2023-11-07更新算法 / LeetCode5 分钟读完 (大约709个字)

找到冠军 I

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

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$ 的节点是否只有一个。

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，要求最大分数，可以先求损失的最小分数，然后使用总分减去该分数即可。

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]);
    }
}

也可以直接正向做，对于每个节点有两种情况：选择当前节点，要求该节点的每个子树都是健康的；不选当前节点，该节点的所有子节点都可以选。

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，直接看灵神代码吧。

// 作者：灵茶山艾府
// 链接：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;
    }
}

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

Educational Codeforces Round 157 (Rated for Div. 2)

Treasure Chest

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

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$ 坐标序列。可以证明，这是最优的。

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

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

首先构造满足第二个条件的数组 $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$ 的数量就需要进行异或操作。

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

2023-11-03发表2023-12-21更新数据库 / OceanBase2 分钟读完 (大约342个字)

2023 OceanBase 数据库大赛

比赛信息

使用 Docker 搭建开发环境

启动报错 Docker Desktop - Unexpected WSL error，搜索半天解决方案，结果是没开 Windows Hypervisor Platform，解决方案在此。
如何在 CLion 中使用 Docker。
遇到 CLion 的 Bug，在 CLion 内置的 Docker 终端无法进行输入，我们直接使用 Docker 客户端打开终端。
终端使用上下左右方向键显示奇怪的编码，似乎是因为默认使用的是 shell，它不支持方向键，我们可以使用 bash 来解决问题，解决方案。
使用 build 构建项目时，报错 $'\r': command not found，这是 Windows 的换行符和 Linux 不同导致的。为了避免在 clone 时进行换行符的转换，可以添加 autocrlf=false 到全局配置文件，或者可以在克隆的命令中添加该参数，更多详细的设置方法可以参考 GitHub 文档。