浙江龙网

  1. 首页 > 生活百科 > >

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 维护某个元素上一次的询问结果 ， 下一次询问这个元素时直接从上一次结果开始 。

推荐阅读


上一篇：C# 7.0 添加和增强的功能【基础篇】

下一篇：Filter Spring中过滤器和拦截器(Interceptor)的区别和联系