比赛链接
A题解知识点：枚举 。
只要一个Q后面有一个A对应即可，从后往前遍历，记录A的数量，遇到Q则数量减一，如果某次Q计数为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\) 是最优答案 。交错构造，\(i+\lfloor \frac{n}{2} \rfloor\) 和 \(i\)，注意 \(i\) 从 \(1\) 到 \(\lfloor \frac{n}{2} \rfloor\)，在最后如果 \(n\) 是奇数则补一个 \(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\) 数 \(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题解知识点：数论，贪心 。
记录每个数字出现的次数，尝试从小到大合成出 \(x\)。从 \(1\) 开始往后遍历，每次将 \(i\) 合成 \(i+1\)，显然 \(i+1\) 个 \(i\) 将产生 \(1\) 个 \(i+1\)。如果出现非 \(x\) 的数 \(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;}