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

比赛链接
A题解知识点：贪心，数论。
先求出序列最大公约数 \(d\)，如果为 \(1\) 直接输出 \(0\)。
否则，尝试用最后一个数操作，\(gcd(d,n) = 1\) 则可以，花费为 \(1\)。
否则，用倒数第二个数操作，\(gcd(d,n-1) = 1\) （不必担心 \(n-1 = 0\)，因为此时上一步一定成功），花费为 \(2\)。
否则，用倒数两个数操作，一定成功，因为 \(gcd(n-1,n)=1\) ，花费为 \(3\)。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[27];bool solve() {int n;cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];int d = a[1];for (int i = 2;i <= n;i++) d = __gcd(a[i], d);if (d == 1) cout << 0 << '\n';else if (__gcd(d, n) == 1) cout << 1 << '\n';else if (__gcd(d, n - 1) == 1) cout << 2 << '\n';else cout << 3 << '\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题解知识点：贪心。
显然左侧已经排好的不用管，从第一段 \(1\) 开始记录后面一共分成的段数 \(cnt\)（如 0000|111|00|1|0|1|0 有 \(6\) 段）。若 \(cnt > 1\) ，则从第一段开始使用操作，每次可以将一段变为 \(0\) （后面也会改变），直到最后一段不用更改，一共操作 \(cnt-1\) 次。另外，如果 \(cnt = 0\) ，答案也是 \(0\)。
【Div. 2 Codeforces Round #830A-D】时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {int n;cin >> n;string s;cin >> s;s = "?" + s;bool st = 0;int cnt = 0;for (int i = 1;i <= n;i++) {if (s[i] != st + '0') {cnt++;st ^= 1;}}cout << max(cnt - 1, 0) << '\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题解知识点：枚举，双指针，位运算，前缀和，贪心。
因为异或相当于不进位的加法，那么前缀和减去前缀异或和一定是非减的，于是一个贪心的结论：最大值一定是 \(f(L_i,R_i)\)的值。接下来需要用这个值，求一个最小区间。
为了方便区间运算，我们预处理一个前缀和，以及一个前缀异或和。
可以证明，最多删除 \(31\) 个非 \(0\) 元素，否则区间值必然减小。因为在 int 范围内，\(31\) 个二进制位，最多能分配给 \(31\) 个数一个不同为值的 \(1\)，这样能使这 \(31\) 个数对答案没有贡献，实际情况不会超过 \(31\) ，因此我们放心大胆的枚举端点就行了。我们只需要考虑非 \(0\) 点，遍历一遍存一下非 \(0\) 点坐标即可。左端点从左往右，内循环右端点从右往左，区间等于最大值的如果长度更小就更新答案。
另外，需要特判没有非 \(0\) 元素的情况，此时直接输出 \(L,L\) 即可。
时间复杂度 \(O(n+q\log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int a[100007];ll sum[100007], sumx[100007];bool solve() {int n, q;cin >> n >> q;for (int i = 1;i <= n;i++) cin >> a[i];vector<int> pos;for (int i = 1;i <= n;i++) {sum[i] = sum[i - 1] + a[i];sumx[i] = sumx[i - 1] ^ a[i];if (a[i]) pos.push_back(i);}while (q--) {int L, R;cin >> L >> R;int l = lower_bound(pos.begin(), pos.end(), L) - pos.begin();int r = upper_bound(pos.begin(), pos.end(), R) - pos.begin() - 1;auto get = [&](int _l, int _r) {return sum[_r] - sum[_l - 1] - (sumx[_r] ^ sumx[_l - 1]);};ll val = get(L, R);int ansl = 0, ansr = n + 1;for (int i = l;i <= r;i++) {if (get(pos[i], pos[r]) < val) break;//可以证明无论左右端点至多删除31个非0元素对答案没有影响（0，2，4 ， 8，...鸽巢原理）for (int j = r;j >= i;j--) {if (get(pos[i], pos[j]) < val) break;if (pos[j] - pos[i] + 1 < ansr - ansl + 1) {ansl = pos[i];ansr = pos[j];}}}if (ansr - ansl + 1 > n) cout << L << ' ' << L << '\n';else cout << ansl << ' ' << ansr << '\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;}D1题解知识点：STL，枚举。
用一个 set<ll> vis 维护出现过的元素，再用一个 map<ll,ll> last 维护某个元素上一次的询问结果，下一次询问这个元素时直接从上一次结果开始。

Div. 2 Codeforces Round #830 A-D

推荐阅读

炒薏米怎么吃最除湿薏米怎么吃除湿效果好呢

另一个伊甸拉克雷娅技能介绍,技能提升

阿房宫赋翻译全文阿房宫赋翻译

关于环球法律评论简述环球法律评论

怎么用CE去查找游戏的技能基址（怎么恢复用ce修改的游戏)

元旦能回河北吗 2022元旦可以回河北吗

儿童买什么保险好

社保交15年和17年的区别相差多少钱？最低要交多少年？

未知错误3004怎么回事？未知错误3004的解决方法[推荐]

光遇禁阁光之翼有几个

法律系实习周记

王者荣耀钻石有什么用-钻石作用详解

1972年属鼠的人婚配查询表

枣花馒头花样做法枣花馒头花样制作方法

双子座的智商有多高

桃花劫是什么意思以及最后的结果

蜻蜓的比喻句怎么写有关蜻蜓的比喻句

黑潮之上艾尔莎好用吗,艾尔莎卡牌技能全面评测,欢迎阅读

散养鸡技术散养鸡蛋和养殖鸡蛋的区别

世上最大的蜈蚣在哪里有多大