经验总结

  1. 首页 > 生活 > >

Div. 3 Codeforces Round #828 A-F

生活百科

比赛链接
A题解知识点：贪心，模拟 。
遇到没用过的数字就给个字母，遇到用过的数字就对照字母是否一致 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[57];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];string s;cin >> s;s = "?" + s;map<int, char> vis;for (int i = 1;i <= n;i++) {if (!vis.count(a[i])) vis[a[i]] = s[i] - 'a';if (vis[a[i]] != s[i] - 'a') return false;}cout << "YES" << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << "NO" << '\n';}return 0;}B题解知识点：数学，模拟 。
记录奇数数量，每次模拟一下变化即可 。
时间复杂度 \(O(n+q)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n, q;cin >> n >> q;ll sum = 0;int cnt1 = 0;for (int i = 1;i <= n;i++) {int x;cin >> x;sum += x;if (x & 1) cnt1++;}while (q--) {int op, x;cin >> op >> x;if (op == 0) {sum += 1LL * (n - cnt1) * x;if (x & 1) cnt1 = n;}else {sum += 1LL * cnt1 * x;if (x & 1) cnt1 = 0;}cout << sum << '\n';}return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}C题解知识点：枚举，模拟 。
\(last\) 存当前位置右边第一个绿灯 。把 \(s\) 复制一遍到后面，方便最后一个绿灯的后面一段也能被算到 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;char ch;cin >> n >> ch;string s;cin >> s;s = "?" + s + s;int last = 0;int ans = 0;for (int i = 2 * n;i >= 1;i--) {if (s[i] == 'g') last = i;else if (s[i] == ch) ans = max(ans, last - i);}cout << ans << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}D题解知识点：数论，贪心 。
先把原来数字的 \(2\) 因子个数加到 \(sum\)。然后再把 \([1,n]\) 的每个数的 \(2\) 因子存起来，贪心地从大到小拿，这样次数最小，直到 \(sum\) 超过 \(n\) 或取完所有数字 。最后小于 \(n\) 则 \(-1\)，否则输出操作次数 。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;int sum = 0;vector<int> tb2;for (int i = 1;i <= n;i++) {int x;cin >> x;while (x % 2 == 0) sum++, x /= 2;x = i;int idx = 0;while (x % 2 == 0) idx++, x /= 2;if (idx) tb2.push_back(idx);}sort(tb2.begin(), tb2.end(), [&](int a, int b) {return a > b;});int cnt = 0;for (auto x : tb2) {if (sum >= n) break;sum += x;cnt++;}if (sum < n) return false;else cout << cnt << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}E题解知识点：dfs，数论，质因数分解 。
题目要求找到 \(x \in (a,c],y \in (b,d]\) 满足 \(a\cdot b | x \cdot y\)。
显然 \(x,y\) 需要分摊到 \(a\cdot b\) 的所有质因子，即 \(x,y\) 一定是 \(a\cdot b\) 两个成对因子 \(f_1,f_2\) 的倍数 。
注意到 \(10^{18}\) 内的数，因子数最多有 \(103680\) 个 ；\(10^9\) 内的数，因子数最多有 \(1344\) 个 。因此，我们不妨先枚举 \(x\) 可能分摊到的因子 \(f_1(f_1 \leq c)\)，同时可以求出另一个因子 \(f_2(f_2\leq d)\)，最后将他们分别加倍到比 \(a\) 和 \(b\) 大，最终检验一下是否还在区间即可 。

经验总结扩展阅读


上一篇：2023年农历八月十二送葬吉日 2023年9月26日适合送葬吗

下一篇：Arctic 基于 Hive 的流批一体实践