比赛链接
A题解知识点:贪心 。
我们考虑把正数和负数分开放,显然把负数和正数放在一起的结果不会更优 。
时间复杂度 \(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\) 个合并最后变成两个奇数区间 , 因此一定存在奇数划分 。
- 其他情况无解 。
map
记录到 \(i\) 之前所有出现的异或和最后一次出现的位置,分奇数下标偶数下标分别记录 。那么对于一个位置 \(i\) ,我们就能找到左侧最近的一个不同奇偶性的位置 \(last[i]\) ,使得 \([1,i]\) 和 \([1, last[i] ]\) 的异或和相同,且 \((last[i],i]\) 区间长度为奇数,于是我们就找到了一个划分点 。如果划分点小于 \(l\) 则不可划分 。时间复杂度 \(O(n \log n + q)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>#define ll long longusing namespace std;int a[200007], xsum[200007], last[200007];ll sum[200007];bool solve() {int n, q;cin >> n >> q;for (int i = 1;i <= n;i++) {cin >> a[i];sum[i] = sum[i - 1] + a[i];xsum[i] = a[i] ^ xsum[i - 1];}map<int, int> mp[2];for (int i = 1;i <= n;i++) {if (mp[!(i & 1)].count(xsum[i])) last[i] = mp[!(i & 1)][xsum[i]];mp[i & 1][xsum[i]] = i;}while (q--) {int L, R;cin >> L >> R;if ((xsum[R] ^ xsum[L - 1]) == 0) {if (sum[R] - sum[L - 1] == 0) cout << 0 << '\n';else if ((R - L + 1) & 1 || !a[L] || !a[R]) cout << 1 << '\n';else if (last[R] >= L) cout << 2 << '\n';else cout << -1 << '\n';}else cout << -1 << '\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;}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- Div. 3 Codeforces Round #820 A-G
- Codeforces 1670 E. Hemose on the Tree
- Div. 1 + Div. 2 Codeforces Round #831 A-E
- Codeforces Global Round 23 A-D
- Div. 4 Codeforces Round #827 A-G
- Div. 3 Codeforces Round #826 A-E
- Div. 3 Codeforces Round #828 A-F
- Div. 2 CF Round #829 题解
- Codeforces 1672 E. notepad.exe
- Div. 2 Codeforces Round #830 A-D