浙江龙网

  1. 首页 > 生活百科 > >

Div. 3 Codeforces Round #820 A-G

生活百科

比赛链接
A题解知识点：模拟
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int a, b, c;cin >> a >> b >> c;int x = a - 1;int y = abs(b - c) + c - 1;if (x > y) cout << 2 << '\n';else if (x < y) cout << 1 << '\n';else cout << 3 << '\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;}B题解知识点：模拟 。
倒着来，很方便 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;string T;cin >> T;string S;for (int i = T.length() - 1;i >= 0;i--) {if (T[i] == '0') {S = (char)((T[i - 1] - '0') + (T[i - 2] - '0') * 10 + 'a' - 1) + S;i -= 2;}else {S = (char)(T[i] - '0' + 'a' - 1) + S;}}cout << S << '\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题解知识点：贪心，枚举 。
【Div. 3 Codeforces Round #820A-G】显然最小花费是 \(|s[n]-a[1]|\) ，最大化路线的方式是按序走过 \(s[1]\) 到 \(s[n]\) 的所有字母 。
把每个字母的下标放进桶中 ， \(s[1]\) 比 \(s[n]\) 小则从 \(s[1]\) 正序，否则从 \(s[1]\) 倒序 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {string s;cin >> s;int n = s.length();s = "?" + s;vector<vector<int>> v(26);for (int i = 1;i <= n;i++) {v[s[i] - 'a'].push_back(i);}int x = s[1] - 'a', y = s[n] - 'a';if (x < y) {int cnt = 0;for (int i = x;i <= y;i++) {cnt += v[i].size();}cout << abs(s[n] - s[1]) << ' ' << cnt << '\n';for (int i = x;i <= y;i++)for (auto j : v[i]) cout << j << ' ';}else {int cnt = 0;for (int i = x;i >= y;i--) {cnt += v[i].size();}cout << abs(s[n] - s[1]) << ' ' << cnt << '\n';for (int i = x;i >= y;i--)for (auto j : v[i]) cout << j << ' ';}cout << '\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题解知识点：贪心，枚举，双指针 。
处理出 \(y-x\) 得到每个成员的贡献，从小到大排序 ， 最小的和最大的两人一组即可最大化分组数量 ， 不能分配就跳过较小的 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int diff[100007];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> diff[i];for (int i = 1;i <= n;i++) {int y;cin >> y;diff[i] = y - diff[i];}sort(diff + 1, diff + n + 1);int ans = 0;int l = 1, r = n;while (l < r) {if (diff[l] + diff[r] >= 0) ans++, r--;l++;}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;}E题解知识点：贪心 。
\(i\) 从 \(2\) 开始依次询问 。先询问 \((1,i)\)，如果结果 \(-1\) 则输出 \(i-1\) ；否则 ， 再询问一次 \((i,1)\)，如果答案和 \((1,i)\) 不同则输出两个答案之和，否则继续下一个 \(i\)。除去特判 \(n \in [3,25]\) 会因为询问到 \(-1\) 结束的情况，其他情况只需要一组答案不同即可 ， 概率很高 。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;ll query(ll a, ll b) {cout << "? " << a << ' ' << b << endl;ll ans;cin >> ans;return ans;}void answer(ll x) {cout << "! " << x << endl;exit(0);}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);for (int i = 2;i;i++) {ll ans1 = query(1, i);if (!~ans1) answer(i - 1);ll ans2 = query(i, 1);if (ans1 != ans2) answer(ans1 + ans2);}return 0;}F题解知识点：枚举，前缀和，数论 。
注意到一个数字 \(\mod 9\) 的答案和所有数位加起来 \(\mod 9\) 的答案相同，因此先对 \(s\) 数位预处理模意义前缀和 。
然后处理出所有 \(w\) 长度的串的余数 ， 把串首坐标放进桶中对应余数的位置，只需要存两个最左边的即可 。
对于每组询问，遍历余数 \(a,b\) 满足 \(a \cdot re + b \equiv k \pmod 9\)  ， 其中 \(re\) 为 \([l,r]\) 的余数 。将余数 \(a,b\) 对应的串下标更新一下答案即可，答案可以用

推荐阅读


上一篇：使用jmx exporter采集kafka指标

下一篇：如何免安装使用 Python？推荐 17 个在线的 Python 解释器！