Practice.
A. Bestie
题意
给定一个数组 \(a\)，定义操作为将 \(a_i\) 改为 \(gcd(a_i, i)\)，代价为 \(n - i + 1\)，输出最小的操作代价总和，使所有数的最大公约数为 \(1\)。
思路
首先，这里有一个结论：相邻数字的最大公约数一定为 \(1\)。
所以，最多只需两次操作，即可满足题意。
所以，我们只需考虑 \(n\) 和 \(n - 1\) 对应的元素是否需要进行操作，以及对应的代价总和的最小值。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f;
int a[N], b[N];
int gcd(int x, int y) {
while (y != 0) {
int tmp = x;
x = y;
y = tmp % y;
}
return x;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --) {
int n;
cin >> n;
int g = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
g = gcd(g, a[i]);
}
if (g == 1) cout << 0 << '\n';
else if (gcd(g, n) == 1) cout << 1 << '\n';
else if (gcd(g, n - 1) == 1) cout << 2 << '\n';
else cout << 3 << '\n';
}
}这结论一开始还真没想到...
B. Ugu
题意
给定一个二进制字符串，定义操作为选定一个整数 \(i\)，将 \([i, n]\) 内的数全都取反，输出让整个字符串变为不递减的操作数的最小值。
思路
考虑下面的模拟：
\(\begin{array}{l}>>01011001011 \\ => 01100110100 \\ => 01111001011 \\ => 01111110100 \\ => 01111111011 \\ => 01111111100 \\ => 01111111111\end{array}\)
也就是说，我们只考虑拐点，统计拐点个数即可。
当然，需要根据第一个数的情况来扣去 \(1\) 或 \(2\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f;
int a[N], b[N];
int gcd(int x, int y) {
while (y != 0) {
int tmp = x;
x = y;
y = tmp % y;
}
return x;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --) {
int n;
cin >> n;
string s;
cin >> s;
char pre = -1;
int dif = 0;
for(int i=0;i<n;i++){
if(pre == -1) pre = s[i];
else{
if(pre != s[i]) dif ++;
pre = s[i];
}
}
dif ++;
cout << max(0ll, dif - (s[0] == '1' ? 1 : 2)) << '\n';
}
}就这么模拟嘞
C1. Sheikh (Easy version)
题意
给定一个数组 \(a\)，定义子区间 \([l, r]\) 的代价 \(f(l, r)\) 为总和和所有数异或值的差。对于 \(q = 1\) 个询问，输出询问的 \([L, R]\) 内的子区间的代价最大值，以及对应的最短区间。
思路
首先，对于一段区间，我们加上一个值 \(x\)，那么总和会改变 \(x\)，而异或值改变量不会超过 \(x\)，也就是说，\(f(l, r) \leq f(l, r + 1)\)。
因而，代价最大值一定是 \(f(L, R)\)，我们只需找出最短区间即可。
因为本题 \(easy\) 难度的数据量低，所以我们不妨直接二分长度，然后枚举所有可行解即可。
使用前缀和和前缀异或优化复杂度。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f;
int a[N], sum[N], xo[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t;
cin >> t;
while(t --) {
int n, q;
cin >> n >> q;
for(int i=1;i<=n;i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
xo[i] = xo[i - 1] ^ a[i];
}
while(q --){
int l, r;
cin >> l >> r;
int ans = (sum[r] - sum[l - 1]) - (xo[r] ^ xo[l - 1]);
int L = 1, R = r - l + 1, mid;
int ansL = l, ansR = r;
while(L < R){
mid = (L + R) >> 1;
bool f = false;
for(int i=l;i+mid-1<=r;i++){
if((sum[i+mid-1] - sum[i - 1]) - (xo[i+mid-1] ^ xo[i - 1]) == ans) {
if(mid < ansR - ansL + 1){
ansL = i, ansR = i + mid - 1;
f = true;
}
}
}
if(f) R = mid;
else L = mid + 1;
}
cout << ansL << ' ' << ansR << '\n';
}
}
}想不到结论就寄
C2. Sheikh (Hard Version)
待补充
D. Balance (Easy version)
题意
给定一个初始情况下只有一个元素 \(0\) 的序列，对于下述两种询问，进行对应的操作：
\(+\ x\)：将 \(x\) 加入序列，满足 \(x\) 原先不在序列里；
\(?\ x\)：输出第一个能被 \(x\) 整除且不在序列里的数。
思路
我们先来考虑纯暴力：对于加上某个数，标记一下这个数已加入；对于查询，暴力枚举其倍数，第一个未被标记的数即为答案。
因为数据量过大，我们考虑用 \(map\)。
纯暴力是不可行的，但我们可以略微优化一下：另开一个 \(map\)，记录这个数的下一个没有被标记的数是什么，若这个数是 \(0\)，那么就是这个数本身，输出即可。
因而，在每次输出的时候，我们可以预处理之后的查询，从而降低复杂度。
对于 \(easy\) 难度，到此即可过。
时间复杂度：不好说
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int q;
cin >> q;
map<int, bool> mp;
map<int, int> to;
while(q --){
char op;
int num;
cin >> op >> num;
mp[0] = true;
if(op == '+') {
mp[num] = true;
}else {
while(mp[to[num]]) to[num] += num;
cout << to[num] << '\n';
}
}
}数据结构题挺少见
D2. Balance (Hard version)
题意
给定一个初始情况下只有一个元素 \(0\) 的序列，对于下述两种询问，进行对应的操作：
\(+\ x\)：将 \(x\) 加入序列，满足 \(x\) 原先不在序列里；
\(-\ x\)：将 \(x\) 从序列中删除，满足 \(x\) 原先在序列里；
\(?\ x\)：输出第一个能被 \(x\) 整除且不在序列里的数。
思路
我们可以继续之前的优化，但这里需要考虑删除数以后，该数的因数 是否已经将 其 下一个未被标记的数 标为大于等于 这个数 的值了。
也就是说，删除以后，我们需要更新这些因数。
暴力枚举因数是不可行的，但考虑到这些因数都是后来加进来的，所以我们可以在上一题输出优化部分，加上 下一个未被标记的数的原数字是什么（也就是它的因子）。然后，在加减操作的时候，我们不妨遍历我们之前记录下来的因子，标记一下这个因子对应原数字有没有被删去。
最后，我们只需按之前的操作，找出该数字下一个未被标记的数，然后判断这个数的倍数有没有已被删去的数，有的话两个数取最小值即可。
时间复杂度：有点小复杂
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N = 2e5 + 10, inf = LONG_LONG_MAX, mod = 998244353;
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int q;
cin >> q;
map<int, bool> mp;
map<int, int> to;
map<int, set<int>> vis, del;
mp[0] = true;
while(q --){
char op;
int num;
cin >> op >> num;
if(op == '+') {
for(auto &i : vis[num]) del[i].erase(num);
mp[num] = true;
}else if(op == '-'){
for(auto &i : vis[num]) del[i].insert(num);
mp[num] = false;
}else{
while(mp[to[num]]) vis[to[num]].insert(num), to[num] += num;
cout << min(to[num], del[num].empty() ? inf : *del[num].begin()) << '\n';
}
}
}数据结构题挺少见，这种简短的题更少见（（