Div. 2 Codeforces Round #832 A-D _生活百科

比赛链接
A题解知识点：贪心。
我们考虑把正数和负数分开放，显然把负数和正数放在一起的结果不会更优。
【Div. 2 Codeforces Round #832A-D】时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;ll sum1 = 0, sum2 = 0;for (int i = 1;i <= n;i++) {int x;cin >> x;if (x >= 0) sum1 += x;else sum2 += -x;}cout << max(sum2 - sum1, sum1 - sum2) << '\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题解知识点：构造。
为了破坏每个子序列，我们把 B 扔到最后面即可，但这样太麻烦，还要考虑跳过后面本来就有的 B。
因此我们选择首末 B 和 N 交换，这样只需要进行一半的对称操作。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;cout << (n + 1) / 2 << '\n';for (int i = 1, j = 3 * n;i < j;i += 3, j -= 3) {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;}C题解知识点：博弈论。
如果 \(\forall i\in [2,n]\) 都有 \(a_1\leq a_i\)，A 无论怎么取，不妨假设取了下标 \(i\)，只要 B 取相同下标的，就会导致 \(a_1-1 \cdots a_i-1\cdots\)，回到这种局面，并且数字减一，往复如此，\(a_1\) 会在 A 的回合是 \(0\) 于是输了。
如果 \(\exist i\in[2,n]\) 有 \(a_1>a_i\)，A 取 \(a_i\) 中最小的那个，就到了 \(\forall i\in [2,n]\) 都有 \(a_1\leq a_i\) 但 B 先手的局面，B 输。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[100007];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];bool ok = 0;for (int i = 2;i <= n;i++) {ok |= a[1] > a[i];}cout << (ok ? "Alice" : "Bob") << '\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题解知识点：贪心，枚举，STL，前缀和。
几个结论：

操作的区间不会交叉。因为交叉一定可以合并成一个完整的区间操作，答案不变，所以操作一定是互不相交的。
区间能操作至 \(0\) 的必要条件是异或和为 \(0\)。因为操作本质是异或和，能合并，如果操作可行则合并得到整个区间的异或和也是 \(0\)。

考虑处理出前缀和，和前缀异或和方便计算。在满足必要条件下分类讨论，不满足的无解：

区间全是 \(0\)，不需要操作。
否则，区间长度为奇数，整个操作一次。
否则，若首或尾有 \(0\) 元素，则可以拆一个出来得到情况2，操作一次即可。
否则，找到区间内某个分割点，使得区间划分成两个长度为奇数异或和为 \(0\) 的区间，回到情况2，操作两次即可。
注意，不需要考虑划分成两个偶数长度区间，如果有偶数长度划分可行，则一定分别能再被划分成两个奇数长度区间，即得到四个奇数长度异或和为 \(0\) 的区间，取前 \(3\) 个合并最后变成两个奇数区间，因此一定存在奇数划分。
其他情况无解。

最后考虑情况4如何找到划分点。我们用