比赛链接
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\) 大，最终检验一下是否还在区间即可 。
时间复杂度 \(O(10^5)\)
空间复杂度 \(O(10^5)\)
代码【Div. 3 Codeforces Round #828A-F】#include <bits/stdc++.h>#define ll long longusing namespace std;int cnt;bool vis[100007];int prime[100007];void euler_screen(int n) {for (int i = 2;i <= n;i++) {if (!vis[i]) prime[++cnt] = i;for (int j = 1;j <= cnt && i * prime[j] <= n;j++) {vis[i * prime[j]] = 1;if (i % prime[j] == 0) break;}}}int a, b, c, d;vector<pair<int, int>> fd;ll val;vector<int> af;void dfs(int step, ll mul) {if (mul > c) return;if (step == fd.size()) {if (val / mul <= d) af.push_back(mul);return;}for (int i = 0;i <= fd[step].second;i++) {dfs(step + 1, mul);mul *= fd[step].first;}}bool solve() {cin >> a >> b >> c >> d;map<int, int> mp;int tt = a;for (int i = 1;prime[i] * prime[i] <= tt;i++) {while (tt % prime[i] == 0) mp[prime[i]]++, tt /= prime[i];}if (tt > 1) mp[tt]++;tt = b;for (int i = 1;prime[i] * prime[i] <= tt;i++) {while (tt % prime[i] == 0) mp[prime[i]]++, tt /= prime[i];}if (tt > 1) mp[tt]++;fd.clear();for (auto [x, y] : mp) fd.push_back({ x,y });af.clear();val = 1LL * a * b;dfs(0, 1);int ansx = -1, ansy = -1;for (auto x : af) {int y = val / x;x = (a / x + 1) * x;y = (b / y + 1) * y;if (x <= c && y <= d) {ansx = x;ansy = y;break;}}cout << ansx << ' ' << ansy << '\n';return 1;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;euler_screen(100001);while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}