力扣 第 399 场周赛 解题报告 | 珂学家 | 调和级数 + 分块DP

---

前言

T1. 优质数对的总数 I

题型: 签到

class Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:res = 0for v1 in nums1:for v2 in nums2:if v1 % (v2 * k) == 0:res += 1return res

---

T2. 压缩字符串 III

思路: 模拟

感觉引入一个栈，操作更加的方便

当然加限制的分组循环也可以

class Solution:def compressedString(self, word: str) -> str:stk = []for i, c in enumerate(word):if len(stk) == 0 or stk[-1][0] != c or stk[-1][1] == 9:stk.append([c, 1])else:stk[-1][1] += 1return ''.join(map(lambda x: str(x[1]) + x[0], stk))

---

T3. 优质数对的总数 II

思路: 调和级数

很典的结论题，时间复杂度为$O(nlogn)$
$$\sum _{i=1}^{i=n}1/i=log(n)$$

class Solution:def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:        mp1 = Counter()for v in nums1:if v % k == 0:mp1[v//k] += 1if len(mp1) == 0:return 0mz = max(mp1.keys())res = 0mp2 = Counter(nums2)for (k1, v1) in mp2.items():for i in range(1, mz // k1 + 1):res += v1 * mp1[i * k1]return res

---

T4. 不包含相邻元素的子序列的最大和

思路: 分块 + DP

因为数据规模不大，$O(\sqrt{n}\ast q)$ 在合理的范围内

所以用分块，思路更加的纯朴和简洁。

每次更新块大小内的状态

然后按块间重算最后的整体解

DP 引入块状态， 表示首尾的0-1状态

具体来讲

class Solution {static long inf = Long.MIN_VALUE / 10;static class Block {int l, r;int[] arr;long[][][] pre;int n;public Block(int l, int r, int[] arr) {this.l = l;this.r = r;this.arr = arr;this.n = r - l + 1;pre = new long[n][2][2];}public void modify() {pre[0][0][0] = 0;pre[0][0][1] = inf;pre[0][1][0] = inf;pre[0][1][1] = arr[l];for (int i = 1; i < n; i++) {pre[i][0][0] = Math.max(pre[i - 1][0][0], pre[i - 1][0][1]);pre[i][1][0] = Math.max(pre[i - 1][1][0], pre[i - 1][1][1]);pre[i][0][1] = pre[i - 1][0][0] + arr[l + i];pre[i][1][1] = pre[i - 1][1][0] + arr[l + i];}}long[][] val() {return pre[n - 1];}}public int maximumSumSubsequence(int[] nums, int[][] queries) {int n = nums.length;int z = (int)Math.sqrt(n);int m = (n + z - 1) / z;Block[] blocks = new Block[m];for (int i = 0; i < m; i++) {blocks[i] = new Block(i * z, Math.min((i + 1) * z - 1, n - 1), nums);blocks[i].modify();}long mod = (long)1e9 + 7;long res = 0;for (int i = 0; i < queries.length; i++) {int[] q = queries[i];int p = q[0], x = q[1];int idx = p / z;nums[p] = x;blocks[idx].modify();long[][] dp = new long[m][2];dp[0][0] = Math.max(blocks[0].val()[0][0], blocks[0].val()[1][0]);dp[0][1] = Math.max(blocks[0].val()[0][1], blocks[0].val()[1][1]);for (int j = 1; j < m; j++) {long[][] next = blocks[j].val();dp[j][0] = Math.max(dp[j - 1][0] + Math.max(next[0][0], next[1][0]), dp[j - 1][1] + next[0][0]);dp[j][1] = Math.max(dp[j - 1][0] + Math.max(next[0][1], next[1][1]), dp[j - 1][1] + next[0][1]);}long tmp = Math.max(dp[m - 1][0], dp[m - 1][1]);res = (res + tmp) % mod;res = (res % mod + mod) % mod;}return (int)res;}
}

---

写在最后