【LeetCode第 313 场周赛】忘光光 _生活百科

比赛链接最近不怎么打比赛，不能马上反应过来考察的是什么，全部忘光光了...

6192. 公因子的数目题意：给定 \(a\) 和 \(b\)，问两者的公因子数量数据范围：\(1\leq a,b\leq 1000\)
题解：从 \(1\) 到 \(\min(a,b)\) 暴力枚举判断即可答案为：\(\sum\limits_{i=1}^{min(a,b)} [a\%i==0\ and\ b\%i==0]\)
时间复杂度：\(O(min(a,b))\)
代码：

class Solution {public:int commonFactors(int a, int b) {int ans = 0;for (int i = min(a, b); i >= 1; --i)if (a % i == 0 && b % i == 0) ans += 1;return ans;}};

6193. 沙漏的最大总和题意：给定一个 \(n\times m\) 的矩阵 \(grid\)，问其中所有的满足如下形状的元素之和最大是多少数据范围：\(3\leq n, m\leq 150, 0\leq grid[i][j]\leq 10^6\)

文章插图
题解：如图所示，就是求任意一个形状如上图所示的，A+B+C+D+E+F+G的和最大是多少，那么暴力模拟即可，可以枚举左上角，注意左上角必须保证 \(i+2<n\ and\ j+2<m\)
时间复杂度：\(O(n\times m)\)
代码：

class Solution {public:int maxSum(vector<vector<int>>& g) {int ans = 0;int n = g.size(), m = g[0].size();for (int i = 0; i + 2 < n; ++i)for (int j = 0; j + 2 < m; ++j) {int sum = 0;for (int a = 0; a < 3; ++a)for (int b = 0; b < 3; ++b)sum += g[i + a][j + b];sum = (sum - g[i + 1][j] - g[i + 1][j + 2]);ans = max(ans, sum);}return ans;}};

6194. 最小 XOR题意：给定两个数 \(num1\) 和 \(num2\) ，请你求出一个数 \(x\)，满足 \(x\) 和 \(num2\) 在二进制位上的 \(1\) 数量相同，同时使得 x XOR num1 尽可能小。数据范围：\(1\leq num1, num2\leq 10^9\)
题解：这里令 \(cnt(a)\) 为 \(a\) 的二进制中 \(1\) 的数量分类讨论：

当 \(cnt(num1) == cnt(num2)\)，此时 \(x = num1\) 即为答案
当 \(cnt(num1) > cnt(num2)\)，此时 \(x\) 和 \(num1\) 异或后使得答案尽可能?。?即优先抹去 \(num1\) 的高位二进制 \(1\) 。
当 \(cnt(num1) < cnt(num2)\) ，此时可以将 \(num1\) 中的所有二进制位 \(1\) 全部抹去，此外再从小到大将 \(num1\) 中二进制位为 \(0\) 的对应的位置置为 \(1\)，这样使得答案尽可能?。饫镏恍枰砑?\(cnt(num2)-cnt(num1)\) 个 \(1\)

时间复杂度：\(O(bit)\)，其中 \(bit\) 为 \(int\) 范围内的数二进制位的个数
代码：

class Solution {public:int minimizeXor(int num1, int num2) {int c1 = 0, c2 = 0;for (int i = 0; i < 30; ++i) {if (num1 >> i & 1) c1 += 1;if (num2 >> i & 1) c2 += 1;}if (c1 == c2) return num1;if (c1 > c2) {int sum = 0;for (int i = 29; i >= 0 && c2 > 0; --i)if (num1 >> i & 1) {c2 -= 1;sum |= 1 << i;}return sum;} else {int sum = 0;c2 -= c1;for (int i = 0; i < 30 && c2 > 0; ++i)if (!(num1 >> i & 1)) {c2 -= 1;sum |= 1 << i;}return sum + num1;}}};

6195. 对字母串可执行的最大删除数【【LeetCode第 313 场周赛】忘光光】题意：给定一个长度为 \(n\) 的字符串 \(s\)，每次有两种删除操作：

删除当前整个串 \(s\)
当存在一个 \(i\) 使得 \(s[0:i]==s[i:2\times i]\) ，那么可以删除 \(s[0:i]\)

问最多可以进行多少次删除操作？数据范围：\(1\leq n\leq 4000, s[i]\) 均为小写字母
题解：考虑 \(dp\)，\(f[i]\) 为删除 \(s[i:n]\) 的最多次数。状态转移方程：

直接删除整个串：\(f[i]=1\)
当 \(s[i:i+j]==s[i+j:i+2\times j]: f[i] = \max\limits_{j=1}^{len}\{f[j]+1\}\)

时间复杂度：\(O(n^2)\)，其中由字符串哈希来 \(O(1)\) 判断字符串是否相同
代码：

typedef unsigned long long ull;const ull P = 13331;class Solution {public:int deleteString(string s) {int n = s.size();s = " " + s;vector<ull> h(n + 1, 0);vector<ull> p(n + 1, 1);for (int i = 1; i <= n; ++i) {h[i] = h[i - 1] * P + s[i];p[i] = p[i - 1] * P;}vector<int> f(n + 1, 0);function<int(int)> get = [&](int id) {if (f[id]) return f[id];f[id] = 1;for (int len = 1; id + len * 2 - 1 <= n; ++len) {ull a = (h[id + len - 1] - p[len] * h[id - 1]);ull b = (h[id + len * 2 - 1] - p[len] * h[id + len - 1]);if ((h[id + len - 1] - p[len] * h[id - 1]) == (h[id + len * 2 - 1] - p[len] * h[id + len - 1]))f[id] = max(f[id], get(id + len) + 1);}return f[id];};return get(1);}};