比賽鏈接
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;}