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 維護某個元素上一次的詢問結果 ， 下一次詢問這個元素時直接從上一次結果開始 。

推薦閱讀