Biweekly Contest 157

欢迎大家加QQ群：623375442。这周终于手速场了，简单很多。

100621. Sum of Largest Prime Substrings

给定一个字符串 s，找出可以由其 子字符串 组成的 3个最大的不同质数 的和。

返回这些质数的 总和 ，如果少于 3 个不同的质数，则返回 所有 不同质数的和。

质数是大于 1 且只有两个因数的自然数：1和它本身。

子字符串 是字符串中的一个连续字符序列。

注意：每个质数即使出现在 多个 子字符串中，也只能计算 一次 。此外，将子字符串转换为整数时，忽略任何前导零。

测试样例：

输入：s = "12234"

输出：1469

解释：由 "12234" 的子字符串形成的不同质数为 2 ，3 ，23 ，223 和 1223。最大的 3 个质数是 1223、223 和 23。它们的和是 1469。

解答：

1. 枚举字符串 s 的所有子串（共有 O(n^2) 个），将子串转换为长整型数字（忽略前导零）。
2. 对每个数字调用 isPrime 判断是否为质数，如果是则加入 Set，去重处理。
3. 遍历保存的所有不同质数，使用长度为 3 的数组 max 维护前三大的质数：遇到更大的就插入，并将后续元素依次后移。
4. 若质数集合大小少于 3，则数组中未被赋值的位置保持 0，最终累加并返回即可。

class Solution {
    public long sumOfLargestPrimes(String s) {
        int n = s.length();
        // 用于存储所有不同的质数
        Set<Long> primes = new HashSet<>();

        // 枚举所有子串
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                String sub = s.substring(i, j);
                long x = Long.parseLong(sub); // 忽略前导零转换为数字
                if (isPrime(x)) {
                    primes.add(x); // 若为质数则加入集合
                }
            }
        }

        if (primes.isEmpty()) return 0; // 没有质数则返回 0

        // 维护一个长度为 3 的数组，保存前三大的质数
        long[] max = new long[3];
        for (long p : primes) {
            for (int i = 0; i < 3; ++i) {
                if (p > max[i]) {
                    // 将较小的依次后移
                    for (int j = 2; j > i; --j) {
                        max[j] = max[j - 1];
                    }
                    max[i] = p; // 插入新值
                    break;
                }
            }
        }
        long sum = 0;
        for (long m : max) {
            sum += m; // 累加前三大的质数（不足三时补 0）
        }
        return sum;
    }

    // 判断一个数是否为质数
    private boolean isPrime(long x) {
        if (x <= 1) return false;
        if (x <= 3) return true;
        if (x % 2 == 0 || x % 3 == 0) return false;
        long r = (long) Math.sqrt(x);
        // 6k ± 1 优化试除法
        for (long i = 5; i <= r; i += 6) {
            if (x % i == 0 || x % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

100657. Find Maximum Number of Non Intersecting Substrings

给你一个字符串 word。

返回以 首尾字母相同 且 长度至少为 4 的 不相交子字符串 的最大数量。

子字符串 是字符串中连续的 非空 字符序列。

测试样例：

输入：word = "abcdeafdef"

输出：2

解释: 两个子字符串是 "abcdea" 和 "fdef"。

解答：

1. 预处理字符串 word，记录每个字符在字符串中的所有出现位置，存入 pos[26] 列表。
2. 动态规划 dp[i] 表示处理到下标 i-1 时，能选取的最大不相交子串数量。
3. 遍历位置 i，查看当前字符 c = word.charAt(i) 在 pos[c] 中的第 points[c] 次出现，与其之前的某次出现位置 tmp 构成的子串长度是否 >= 4（即下标差 >= 3）。
4. 若满足长度条件，则 dp[i+1] = max(dp[i], dp[ start_index ] + 1)，否则 dp[i+1] = dp[i]。
5. 最终输出 dp[len] 即可。

class Solution {
    public int maxSubstrings(String word) {
        int len = word.length();
        // pos[o] 存储字符 o ('a' -> 0) 的出现下标列表
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; ++i) {
            pos[i] = new ArrayList<>();
        }
        // 收集所有字符位置
        for (int i = 0; i < word.length(); ++i) {
            int o = word.charAt(i) - 'a';
            pos[o].add(i);
        }
        int[] points = new int[26]; // 记录每个字符当前处理到哪次出现
        int[] dp = new int[len + 1];
        for (int i = 0; i < word.length(); ++i) {
            int o = word.charAt(i) - 'a';
            // tmp 指向前一次可能的开始位置
            int tmp = points[o];
            // 如果子串长度 < 4（差 < 3），则 tmp-- 继续寻找更早位置
            while (tmp >= 0 && pos[o].get(points[o]) - pos[o].get(tmp) < 3) {
                --tmp;
            }
            // 默认不选取以当前位置结尾的子串
            dp[i + 1] = dp[i];
            // 若存在合法的 tmp，则尝试选取该子串
            if (tmp >= 0 && pos[o].get(points[o]) - pos[o].get(tmp) >= 3) {
                // 子串区间为 [ tmp, points[o] ]，长度 >= 4
                dp[i + 1] = Math.max(dp[i + 1], dp[pos[o].get(tmp)] + 1);
            }
            ++points[o]; // 处理下一个出现
        }
        return dp[len];
    }
}

100644. Number of Ways to Assign Edge Weights II

给你一棵有 n 个节点的无向树，节点从 1 到 n 编号，树以节点 1 为根。树由一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间有一条边。

一开始，所有边的权重为 0。你可以将每条边的权重设为 1 或 2。

两个节点 u 和 v 之间路径的 代价 是连接它们路径上所有边的权重之和。

给定一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，计算从节点 ui 到 vi 的路径中，使得路径代价为 奇数 的权重分配方式数量。

返回一个数组 answer，其中 answer[i] 表示第 i 个查询的合法赋值方式数量。

由于答案可能很大，请对每个 answer[i] 取模 10^9 + 7。

注意： 对于每个查询，仅考虑 ui 到 vi 路径上的边，忽略其他边。

测试样例：

输入：edges = [[1,2]], queries = [[1,1],[1,2]]

输出：[0,1]

解释: 查询 [1,1]：节点 1 到自身没有边，代价为 0，因此合法赋值方式为 0。查询 [1,2]：从节点 1 到节点 2 的路径有一条边（1 → 2）。将权重设为 1 时代价为奇数，设为 2 时为偶数，因此合法赋值方式为 1。

解答：

1. 首先将树转换为邻接表 graph，并初始化每个节点的祖先信息 ancestors[node]，用于 LCA（二进制 2^k 跳）查询。
2. 深度优先搜索 dfs 预处理节点深度 depth，并记录 up[0] 父节点。
3. 利用二进制跳表填充所有 up[k]，快速查询任意两点的最近公共祖先 lca(u,v)。
4. 对每个查询 queries[i]，计算节点 u、v 路径上边数 edgeCount = depth[u] + depth[v] - 2*depth[lca]。
5. 该路径上每条边可选权重 1 或 2，总共 2^edgeCount 种方式，其中使得路径代价为奇数的方式数为 2^(edgeCount-1)（固定一个边为 1 决定奇偶，其余自由）。
6. 若 edgeCount==0（同一个节点），没有边且代价为 0（偶数），故答案为 0。
7. 对结果取模 10^9+7 返回即可。

class Solution {
    private static final int mod = 1_000_000_007;

    // 存储二进制跳表和深度信息
    class Ancestor {
        int[] up;   // up[k] 表示 2^k 步以上的祖先
        int depth;  // 节点深度

        public Ancestor(int len) {
            up = new int[len];
            Arrays.fill(up, -1);
        }
    }

    public int[] assignEdgeWeights(int[][] edges, int[][] queries) {
        int n = edges.length + 1;
        int max = 32 - Integer.numberOfLeadingZeros(n);
        List<Integer>[] graph = new List[n];
        Ancestor[] ancestors = new Ancestor[n];
        for (int i = 0; i < n; ++i) {
            graph[i] = new ArrayList<>();
            ancestors[i] = new Ancestor(max);
        }
        // 构建无向树
        for (int[] e : edges) {
            graph[e[0] - 1].add(e[1] - 1);
            graph[e[1] - 1].add(e[0] - 1);
        }
        // DFS 计算深度并设置 up[0]
        dfs(0, -1, 0, ancestors, graph);
        // 二进制跳表预处理
        for (int k = 1; k < max; ++k) {
            for (int node = 0; node < n; ++node) {
                int pre = ancestors[node].up[k - 1];
                ancestors[node].up[k] = (pre == -1 ? -1 : ancestors[pre].up[k - 1]);
            }
        }
        int[] res = new int[queries.length];
        // 处理每个查询
        for (int i = 0; i < queries.length; ++i) {
            int u = queries[i][0] - 1, v = queries[i][1] - 1;
            int parent = lca(u, v, ancestors);
            // 计算路径边数
            int edgeCount = ancestors[u].depth + ancestors[v].depth - 2 * ancestors[parent].depth;
            res[i] = countOddWays(edgeCount);
        }
        return res;
    }

    // 深度优先搜索，设置 up[0] 和 depth
    private void dfs(int cur, int pre, int depth, Ancestor[] ancestors, List<Integer>[] graph) {
        ancestors[cur].up[0] = pre;
        ancestors[cur].depth = depth;
        for (int nxt : graph[cur]) {
            if (nxt != pre) {
                dfs(nxt, cur, depth + 1, ancestors, graph);
            }
        }
    }

    // 计算最近公共祖先
    private int lca(int u, int v, Ancestor[] ancestors) {
        if (ancestors[u].depth < ancestors[v].depth) {
            int t = u; u = v; v = t;
        }
        int diff = ancestors[u].depth - ancestors[v].depth;
        // 把 u 提升到和 v 同一深度
        for (int k = 0; k < ancestors[u].up.length; ++k) {
            if ((diff & (1 << k)) != 0) {
                u = ancestors[u].up[k];
            }
        }
        if (u == v) return u;
        // 同步二进制跳表找 LCA
        for (int k = ancestors[u].up.length - 1; k >= 0; --k) {
            if (ancestors[u].up[k] != ancestors[v].up[k]) {
                u = ancestors[u].up[k];
                v = ancestors[v].up[k];
            }
        }
        return ancestors[u].up[0];
    }

    // 计算使路径代价为奇数的方式数
    private int countOddWays(int edgeCount) {
        if (edgeCount == 0) return 0; // 无边时代价为 0（偶数），返回 0
        return pow(2, edgeCount - 1, mod);
    }

    // 快速幂取模
    private int pow(long base, long exp, int mod) {
        long ans = 1, x = base % mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                ans = (ans * x) % mod;
            }
            x = (x * x) % mod;
            exp >>= 1;
        }
        return (int) ans;
    }
}