比赛链接最近不怎么打比赛,不能马上反应过来考察的是什么,全部忘光光了...6192. 公因子的数目【【LeetCode第 313 场周赛】忘光光】题意:给定 \(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\)
代码:
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]\)
题解:考虑 \(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\}\)
代码:
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);}};
经验总结扩展阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 电视剧醉玲珑角色介绍
- 人为什么会老死呢
- 商场消防验收标准是什么
- 乙肝能引起胃病吗
- 企业的存出保证金应借记什么科目
- a7m3与a7r3区别
- 小孩喝米酒有坏处吗
- 没有成本发票怎么做账
- 三句关于言行一致的名言警句
- 南瓜治胃病怎么吃