比賽鏈接
A題解知識點：枚舉 。
只要一個Q后面有一個A對應即可，從后往前遍歷，記錄A的數(shù)量，遇到Q則數(shù)量減一，如果某次Q計數(shù)為0則NO 。
時間復雜度 \(O(n)\)
空間復雜度 \(O(1)\)
代碼#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;string s;cin >> s;s = "?" + s;int cnt = 0;for (int i = n;i >= 1;i--) {if (s[i] == 'Q') {if (cnt == 0) return false;cnt--;}else cnt++;}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題解知識點：構造 。
可以證明 \(\lfloor \frac{n}{2} \rfloor\) 是最優(yōu)答案 。交錯構造，\(i+\lfloor \frac{n}{2} \rfloor\) 和 \(i\)，注意 \(i\) 從 \(1\) 到 \(\lfloor \frac{n}{2} \rfloor\)，在最后如果 \(n\) 是奇數(shù)則補一個 \(n\)。
時間復雜度 \(O(n)\)
【Div. 2 Codeforces Round #829A-E】空間復雜度 \(O(1)\)
代碼#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;for (int i = 1;i <= n / 2;i++) {cout << i + n / 2 << ' ' << i << ' ';}if (n & 1) cout << n << ' ';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;}C題解知識點：構造 。
可以兩兩構造 。找到一對非 \(0\) 數(shù) \(a[i],a[j]\)，當 \(a[i] = a[j]\)，如果 \(i,j\) 奇偶性相同則 \([i,i],[i+1,j]\)，否則分段 \([i,j]\) ；當 \(a[i] \neq a[j]\)，如果 \(i,j\) 奇偶性相同則 \([i,j]\)，否則 \([i,i],[i+1,j]\)。
注意兩對之間以及首尾可能會存在空隙，最后要把上面答案遍歷一遍，填補空隙 。
時間復雜度 \(O(n)\)
空間復雜度 \(O(n)\)
代碼#include <bits/stdc++.h>#define ll long longusing namespace std;int a[200007];bool solve() {int n;cin >> n;vector<int> pos;for (int i = 1;i <= n;i++) cin >> a[i];for (int i = 1;i <= n;i++) {if (a[i]) pos.push_back(i);}if (pos.size() & 1) return false;if (!pos.size()) {cout << 1 << '\n';cout << 1 << ' ' << n << '\n';return true;}vector<pair<int, int>> v;for (int i = 0;i < pos.size();i += 2) {if (a[pos[i]] == a[pos[i + 1]]) {if ((pos[i] & 1) == (pos[i + 1] & 1)) {v.push_back({ pos[i], pos[i] });v.push_back({ pos[i] + 1,pos[i + 1] });}else v.push_back({ pos[i],pos[i + 1] });}else {if ((pos[i] & 1) != (pos[i + 1] & 1)) {v.push_back({ pos[i], pos[i] });v.push_back({ pos[i] + 1,pos[i + 1] });}else v.push_back({ pos[i],pos[i + 1] });}}vector<pair<int, int>> ans;int prer = 0;for (auto [i, j] : v) {if (i != prer + 1) ans.push_back({ prer + 1, i - 1 });ans.push_back({ i,j });prer = j;}if (ans.back().second != n) ans.push_back({ ans.back().second + 1,n });cout << ans.size() << '\n';for (auto [i, j] : ans) {cout << i << ' ' << j << '\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題解知識點：數(shù)論，貪心 。
記錄每個數(shù)字出現(xiàn)的次數(shù)，嘗試從小到大合成出 \(x\)。從 \(1\) 開始往后遍歷，每次將 \(i\) 合成 \(i+1\)，顯然 \(i+1\) 個 \(i\) 將產(chǎn)生 \(1\) 個 \(i+1\)。如果出現(xiàn)非 \(x\) 的數(shù) \(i\) 不能全部使用，那么整個式子就無法被 \(x!\) 整除 。
時間復雜度 \(O(n)\)
空間復雜度 \(O(1)\)
代碼#include <bits/stdc++.h>using namespace std;int cnt[500007];int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n, x;cin >> n >> x;for (int i = 1;i <= n;i++) {int tmp;cin >> tmp;cnt[tmp]++;}for (int i = 1;i < x;i++) {if (cnt[i] % (i + 1)) {cout << "NO" << '\n';return 0;}cnt[i + 1] += cnt[i] / (i + 1);}cout << "YES" << '\n';return 0;}