浙江龙网

  1. 首页 > 生活百科 > >

Div. 4 Codeforces Round #827 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;if (a + b == c || a + c == b || b + c == a) cout << "YES" << '\n';else cout << "NO" << '\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 \log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;set<int> st;bool ok = 1;for (int i = 1;i <= n;i++) {int x;cin >> x;if (st.count(x)) ok = 0;st.insert(x);}if (ok) cout << "YES" << '\n';else cout << "NO" << '\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题解知识点：贪心 。
行红 ， 列蓝别搞错 。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;char dt[10][10];bool solve() {for (int i = 1;i <= 8;i++)for (int j = 1;j <= 8;j++)cin >> dt[i][j];for (int i = 1;i <= 8;i++) {bool ok = 1;for (int j = 1;j <= 8;j++) ok &= dt[i][j] == 'R';if (ok) {cout << 'R' << '\n';return true;}}for (int j = 1;j <= 8;j++) {bool ok = 1;for (int i = 1;i <= 8;i++) ok &= dt[i][j] == 'B';if (ok) {cout << 'B' << '\n';return true;}}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题解知识点：枚举，数论 。
注意到 \(a_i \in [1,1000]\)，因此贪心地记录 \(a_i\) 最后一次的位置，枚举 \([1,1000]\) 每个数的组合即可 。
时间复杂度 \(O(n+1000^2)\)
【Div. 4 Codeforces Round #827A-G】空间复杂度 \(O(1000)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int vis[1007];bool solve() {int n;cin >> n;memset(vis, 0, sizeof(vis));for (int i = 1;i <= n;i++) {int x;cin >> x;vis[x] = max(vis[x], i);}int ans = -1;for (int i = 1;i <= 1000;i++) {if (!vis[i]) continue;for (int j = i;j <= 1000;j++) {if (!vis[j]) continue;if (__gcd(i, j) == 1) ans = max(ans, vis[i] + vis[j]);}}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题解知识点：二分 ， 前缀和 ， 枚举 。
预处理前缀和方便输出答案，前缀最大值方便找到最大合法段，然后二分查询第一个大于 \(x\) 的位置 \(i\)  ， 则 \([1,i-1]\) 都可以 。
时间复杂度 \(O(n+q\log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;ll a[200007], mx[200007];bool solve() {int n, q;cin >> n >> q;for (int i = 1;i <= n;i++) {cin >> a[i];mx[i] = max(mx[i - 1], a[i]);a[i] += a[i - 1];}while (q--) {int x;cin >> x;int pos = upper_bound(mx + 1, mx + 1 + n, x) - mx - 1;cout << a[pos] << ' ';}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;}F题解知识点：贪心 。
我们可以任意排列且 \(s,t\) 初始有 a  ， 那么如果 \(t\) 具有超过 a 的字母，那么一定可以有 \(s<t\) ；否则，如果 \(s\) 也没有超过 a 的字母且 \(s\) 长度小于 \(t\) ，那么一定可以有 \(s<t\) ；否则一定有 \(t<s\)。
时间复杂度 \(O(q+\sum |s|)\)
空间复杂度 \(O(|s|)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int q;cin >> q;ll cnts = 0, cntt = 0;bool sbad = 0, tgood = 0;while (q--) {int d, k;string x;cin >> d >> k >> x;if (d == 1) {for (auto ch : x) {cnts += k * (ch == 'a');sbad |= ch != 'a';}}else {for (auto ch : x) {cntt += k * (ch == 'a');tgood |= ch != 'a';}}if (tgood) cout << "YES" << '\n';else if (!sbad && cnts < cntt) cout << "YES" << '\n';else cout << "NO" << '\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;}G题解知识点：位运算，贪心，枚举 。

推荐阅读


上一篇：原神3.0乱纹精致宝箱怎么开启

下一篇：JavaScript的异步编程之Promise