A
题解
知识点:模拟。
时间复杂度 \(O(1)\)
空间复杂度 \(O(1)\)
代码
#include #define ll long long using 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 #define ll long long using 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 #define ll long long using 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)\)
空间复杂度 \(O(1000)\)
代码
#include #define ll long long using 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 #define ll long long using 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
的字母,那么一定可以有 \(sa
的字母且 \(s\) 长度小于 \(t\) ,那么一定可以有 \(s 。
时间复杂度 \(O(q+\sum |s|)\)
空间复杂度 \(O(|s|)\)
代码
#include #define ll long long using 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
题解
知识点:位运算,贪心,枚举。
用 \(val\) 记录目前哪个位置还缺 \(1\) 。每次枚举没有取过的数字,找到一个数 \(a[pos]\) 使 a[pos] & val
最大,表示有效位组成最大的数字。然后取出来,并通过 val &= ~a[pos]
把 \(val\) 中对应的 \(1\) 删除(把 \(a[pos]\) 取反,原来的 \(1\) 现在都为 \(0\) ,然后与 \(val\) 就能删掉 \(val\) 对应的 \(1\))。最后把 \(a[pos]\) 交换到末尾的有效数字,实现逻辑删除。
因为 int
有 \(31\) 位,每次删除删的是结果最大的,最多删除 \(31\) 次就能达到这个序列或的最大值。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include #define ll long long using namespace std; int a[200007]; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) cin >> a[i]; int val = ~(1 << 31); for (int i = 1;i <= min(31, n);i++) { int pos = 1; for (int j = 1;j <= n - i + 1;j++) { if ((val & a[j]) > (val & a[pos])) pos = j; } cout << a[pos] << ' '; val &= ~a[pos]; swap(a[n - i + 1], a[pos]); } for (int i = 1;i <= n - min(31, n);i++) cout << a[i] << ' '; 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; }