Codeforces Round #830 (Div. 2) 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 long
using 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\) 。
時間複雜度 \(O(n)\)
空間複雜度 \(O(n)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using 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 long
using 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 維護某個元素上一次的詢問結果，下一次詢問這個元素時直接從上一次結果開始。
每個元素 \(i\) 只經過其倍數一次，共 \(\dfrac{n}{i}\) 次。所有元素次數之和 \(O(\sum \dfrac{n}{i}) = O(n \log n)\) 。
時間複雜度 \(O(q \log^2 q)\)
空間複雜度 \(O(q)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int q;
cin >> q;
set<ll> vis;
map<ll, ll> last;
while (q--) {
char op;
ll x;
cin >> op >> x;
if (op == '+') {
vis.insert(x);
}
else {
if (!last.count(x)) last[x] = x;
while (vis.count(last[x])) last[x] += x;
cout << last[x] << '\n';
}
}
return 0;
}
D2
題解
知識點：STL，枚舉。
因為存在刪除已存在元素的操作，這意味著我們之前得到的答案在未來可能不適用。
因此需要對每個已詢問過的數字維護一個已刪除集合 map<ll,set<ll>> del ，來得到目前某個元素的最大詢問結果之前，是否有在序列中被刪除的倍數。
對於已刪除集合的維護，需要對每個詢問過程中遍歷到的且存在於序列中的倍數維護一個影響列表 map<ll,vector<ll>> chg ，來得到修改序列某個元素的狀態時，哪些詢問過的元素的已刪除集合會被修改。
如此我們就維護了帶刪除求 mex 的數據結構。
時間複雜度 \(O(q \log ^2 q)\)
空間複雜度 \(O(q\log q)\)
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int q;
cin >> q;
set<ll> vis;//序列中存在的元素
map<ll, ll> last;//某元素最大詢問結果：記錄需要維護的數據上界，超出最大詢問結果的不需要考慮
map<ll, set<ll>> del;//某元素的已刪除集合：最大詢問結果內，目前不存在於序列中的倍數
map<ll, vector<ll>> chg;//某元素的影響列表：更改序列中某元素狀態，已刪除集合將發生變化的元素列表
while (q--) {
char op;
ll x;
cin >> op >> x;
if (op == '+') {
vis.insert(x);
for (auto y : chg[x]) del[y].erase(x);//刪除受x影響元素的已刪除集合中的x，因為x已存在
}
else if (op == '-') {
vis.erase(x);
for (auto y : chg[x]) del[y].insert(x);//增加受x影響元素的已刪除集合中的x，因為x已刪除
}
else {
if (!last.count(x)) last[x] = x;//新增已詢問元素
if (del[x].size()) cout << *del[x].begin() << '\n';//已刪除集合存在元素，優先使用
else {//考慮最大詢問結果是否可行，否則擴大最大詢問結果
while (vis.count(last[x])) {
chg[last[x]].push_back(x);//已存在的x的倍數，在未來可能會被修改狀態，影響x的結果
last[x] += x;
}
cout << last[x] << '\n';
}
}
}
return 0;
}
