【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. 对字母串可执行的最大删除数
题意：
给定一个长度为 \(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);
}
};
