Helping the Nature
出处：CF1700C
题目大意：给定 $n$ 个元素，有如下三种操作：
- 选择 $i$ ，将 $a_1,a_2,\ldots,a_i$ 都减少1。
- 选择 $i$ ，将 $a_i,a_{i+1},\ldots,a_n$ 都减少1。
- 将所有 $a_i$ 都增加1。
现在，要使 $a_i$ 全部为0，至少需要执行多少次操作？
数据范围： $1 \leq n \leq 2 \cdot 10^5, -10^9 \leq a_i \leq 10^9$
思路：首先看到区间操作，马上就知道是用差分了。
于是三种操作就可以转变为：
第一种操作相当于在 $diff[i+1]$ 放上 $+1$ ，在 $diff[0]$ 上放上 $-1$ 。
第二种操作相当于在 $diff[n]$ 上放上 $+1$ ，同时在 $diff[i]$ 上放上 $-1$ 。
第三种操作相当于在 $diff[0]$ 上放上 $+1$ ,同时在 $diff[n]$ 上放上 $-1$ 。
于是可以看出，对于中间的项，只能用第一种操作跟第二种操作把它转变为0，最后再使用第三种操作将首尾补成0即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vl diff;
diff.push_back(a[0]);
rep(i, 1, n - 1) diff.push_back(a[i] - a[i - 1]);
diff.push_back(0);
ll ans = 0;
rep(i, 1, n - 1) {
if (diff[i] > 0) {
ans += abs(diff[i]);
diff[n] += abs(diff[i]);
} else if (diff[i] < 0) {
ans += abs(diff[i]);
diff[0] += diff[i];
}
}
if (diff[0] != 0) ans += abs(diff[0]);
cout << ans << endl;
return;
}
|
Simple Permulation
出处：CF2090D
题目大意：请构造一个长度为 $n$ 的排列，使得 $c_i=\lceil \frac{p_1+p_2+\ldots +p_i}{i} \rfloor$ 中，至少有 $\lfloor \frac{n}{3} \rfloor -1$ 个质数。
数据范围： $2 \leq n \leq 10^5$
思路：首先，我们熟悉以下定理：对于任意整数 $x$ ，在 $[x,2x]$ 内必然存在质数。
考虑从 $[\frac{n}{3},\frac{2*n}{3}]$ 中寻找质数，找到质数 $a$ 后，考虑在 $c$ 中构造，构造以下形式： $c,c-1,c+1,c-2,c+2,\ldots$ ，最后再补上剩下的即可。
一种构造思路：调整与抵消，在前面就完成需要的任务，同时也要记熟这个定理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
bool isprime(int x) {
if (x == 1 || x == 0) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
void solve() {
int n;
cin >> n;
vi a;
int p = 0;
rep(i, n / 3, (n * 2 + 2) / 3) {
if (isprime(i)) {
p = i;
break;
}
}
a.push_back(p);
map<int, int> ma;
ma[p]++;
rep(i, 1, n) {
if (p - i > 0) {
a.push_back(p - i);
ma[p - i]++;
}
if (p + i <= n) {
a.push_back(p + i);
ma[p + i]++;
}
}
rep(i, 1, n) {
if (!ma.count(i)) a.push_back(i);
}
rep(i, 0, n - 1) cout << a[i] << ' ';
cout << endl;
return;
}
|
Look Back
出处：CF1883E
题目大意：给定一个整数数组，每次可以给一个数乘2，问使这个数组不递减的最少操作次数？
数据范围： $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$
思路：显然遍历一遍，每次乘2就行，但是这样会爆掉int128,非常阴。
因此，考虑记录每个数乘的次数，再判断即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll ans = 0;
vl x(n);
rep(i, 1, n - 1) {
if (a[i] >= a[i - 1]) {
x[i] = x[i - 1] - 1LL * floor(log2((double)a[i] / a[i - 1]));
x[i] = max(x[i], 0LL);
} else {
x[i] = x[i - 1] + 1LL * ceil(log2((double)a[i - 1] / a[i]));
}
ans += x[i];
}
cout << ans << endl;
return;
}
|
Tandem Repeats?
出处：CF1948D
题目大意：给定一个由小写英文字母和问号组成的字符串 $s$ ，问号可以匹配所有小写英文字母，问最长好子串的长度是多少？这里好子串定义为，长度为偶数，分为两段后前后完全匹配。
数据范围： $1 \leq n \leq 5000$
思路：显然是 $O(n^2)$ 的算法。
匹配题目，这个分段应该是没有kmp，因此直接考虑DP，设 $dp[i][j]$ 为前一段结尾是 $i$ ，后一段结尾是 $j$ 的最长匹配长度，如果能匹配就从 $dp[i-1][j-1]$ 转移，最后取符合条件的最长长度即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void solve() {
string s;
cin >> s;
int n = sz(s);
int ans = 0;
vvi dp(n + 1, vi(n + 1));
rep(i, 1, n) {
rep(j, 1, i - 1) {
if (s[i - 1] == '?' || s[j - 1] == '?' || s[i - 1] == s[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
}
}
rep(i, 1, n) {
rep(j, i + 1, n) {
if (dp[j][i] >= j - i) {
ans = max(ans, 2 * min(dp[j][i], j - i));
}
}
}
cout << ans << endl;
return;
}
|
Railway System
出处：CF1687B
题目大意：给定一个 $n$ 个点 $m$ 条边的无向图，每次查询给出这 $m$ 条边的连通性，输出其中最大生成森林（也就是所有联通分支的最大生成树的边权之和）的值，现在，请在 $2m$ 次查询中找出整个图最小生成树的值。
数据范围： $2 \leq n \leq 200, 1 \leq m \leq 500$
思路：最小生成树，那么就是Kruscal算法。
一个很显然的思路是，我先用 $m$ 次查询把所有的边都查找出来，然后按照最小生成树的思路把他们排序。
但是，原图中查询的是最大生成森林，这怎么联系在一起呢？
考虑最小生成树的性质，任何一个环中的最大边都不可能在最小生成树里，而在加边过程中，如果最大生成森林的增量不是当前的边，那么就说明这里这条边是在某个环里的，又因为排序，因此此时环里的边权值都小于等于这条边，所以它不能加。于是一次次加边，这又是 $m$ 次操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
void ask(string s) {
cout << "? " << s << '\n';
cout.flush();
}
void report(ll sum) {
cout << "! " << sum << '\n';
cout.flush();
}
void solve() {
int n, m;
ll op;
ll tem = 0;
cin >> n >> m;
string res = "";
rep(i, 0, m - 1) res.push_back('0');
vector<pll> ma;
rep(i, 0, m - 1) {
res[i] = '1';
ask(res);
cin >> op;
ma.emplace_back(op, i);
res[i] = '0';
}
sort(all(ma));
rep(i, 0, m - 1) {
string tem2 = res;
tem2[ma[i].second] = '1';
ask(tem2);
cin >> op;
if (op == tem + ma[i].first) {
res = tem2;
tem = op;
} else {
continue;
}
}
report(tem);
return;
}
|
Maximum And Queries(easy)
出处：CF1903D1
题目大意：给定 $n$ 个元素的数组 $a$ ，现在给定 $q$ 个询问，每次询问给出一个 $k$ ，所有的元素可以加 $k$ 次，问此时它们的最大与的值是多少。
数据范围： $1 \leq n,q \leq 10^5, 1 \leq sum(n \cdot q) \leq 10^5,0 \leq a_i \leq 10^6, 0 \leq k_i \leq 10^{18}$
思路：力扣题目，一眼试填法，注意这里莫名其妙会爆long long，所以用int128。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
void solve() {
int n, q;
cin >> n >> q;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll k;
rep(i, 0, q - 1) {
cin >> k;
ll ans = 0;
frep(j, 60, 0) {
i128 tem = 0;
ll ans2 = ans + (1LL << j);
rep(v, 0, n - 1) {
ll val = a[v];
frep(l, 60, 0) {
if ((ans2 >> l) & 1) {
if (!((val >> l) & 1)) {
tem += (i128)((1LL << l) - (val & ((1LL << l) - 1)));
val += (i128)((1LL << l) - (val & ((1LL << l) - 1)));
}
}
}
}
if (tem <= k) {
ans += (1LL << j);
}
}
cout << ans << endl;
}
return;
}
|
Bitwise Operation Wizard
出处：CF1937C
题目大意：给定一个 $0 \sim n-1$ 的排列，每次查询输入四个数 $a,b,c,d$ 会给出 $p_a | p_b $ 与 $p_c | p_d$ 的大小关系，请在 $3n$ 次查找内给出 $i,j$ ，使得 $p_i \bigoplus p_j$ 最大。
数据范围： $1 \leq n \leq 10^4$
思路：首先，回顾一下什么样的情况会使异或和最大？
一种显然的情况就是，取 $n-1$ 然后把它为 $0$ 的位都填满。
所以，这里我们首先可以用 $n$ 次查询来找出最大值的位置。
接着，怎么找把它为 $0$ 的位置填满？注意这个数和 $n-1$ 的或运算，也是所有数与 $n-1$ 的或运算能得到的最大值，并且它是满足以上条件中最小的数，因此首先用 $n$ 次查询找出所有符合条件的数，再用最多 $n$ 次查询找出其中最小的数，即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
void ask(int l, int r, int a, int b) {
cout << "? " << l << ' ' << r << ' ' << a << ' ' << b << '\n';
cout.flush();
}
void report(ll sum, ll sum2) {
cout << "! " << sum << ' ' << sum2 << '\n';
cout.flush();
}
void solve() {
int n;
cin >> n;
int idx = 0;
int idx2 = 0;
char op;
rep(i, 1, n - 1) {
ask(idx, idx, i, i);
cin >> op;
if (op == '>')
continue;
else {
idx = i;
}
}
vi res;
int idx4 = (idx == 0) ? 1 : 0;
int idx3 = idx4;
res.push_back(idx4);
rep(i, 0, n - 1) {
if (i == idx || i == idx4) continue;
ask(idx, idx4, idx, i);
cin >> op;
if (op == '=')
res.push_back(i);
else if (op == '<') {
res.clear();
res.push_back(i);
idx4 = i;
} else
continue;
}
int m = sz(res);
rep(i, 1, m - 1) {
ask(res[idx2], res[idx2], res[i], res[i]);
cin >> op;
if (op == '>')
idx2 = i;
else
continue;
}
report(idx, res[idx2]);
return;
}
|
RPD and Rap Sheet(easy)
出处：CF1543D1
题目大意：交互题，现在有一个 $[0,n-1]$ 之间的密码 $x$ ，需要你每次猜一个密码 $y(0 \leq y \leq 2 \cdot 10^7)$ ，接着如果猜对则游戏结束，如果猜错， $x$ 会变为 $x \bigoplus z = y$ 的 $z$ ，请在 $n$ 次猜测中猜中密码。
数据范围： $1 \leq n \leq 2 \cdot 10^5$
思路：这里给出一个互动游戏中的常见思路，也就是如果对面是动态变化的，那么尽可能让它回复原状。
于是，考虑什么呢？如果按照这样的次序输入，也就是 $0 \bigoplus 1,1 \bigoplus 2,\ldots (n-1) \bigoplus n$ ，那么对于任意次数之前的，就能抵消掉前面的所有内容，只剩下该项的右操作数，于是就做完了，裂项好方法。
这道题看了题解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void ask(int l) {
cout << l << '\n';
cout.flush();
}
void solve() {
int n, k;
cin >> n >> k;
int op;
ask(0);
cin >> op;
if (op == 1) return;
rep(i, 0, n - 2) {
ask(i ^ (i + 1));
cin >> op;
if (op == 1) return;
}
return;
}
|
Smile and Minecraft
出处： CF2113C
题目大意：给定一个 $n \times m$ 的矩阵，其中有石头、金子和空地，每次可以在空地上装一个炸弹，以该点为中心，边长为 $2k+1$ 的正方形都会被炸成空地，但是紧挨着整个正方形的黄金都会被收集，现在要问：能收集的最大黄金数量是多少？
数据范围： $1 \leq n,m,k \leq 500, 1 \leq sum(n \cdot m) \leq 2.5 \cdot 10^5$
思路：一看到这道题，第一反应是二维前缀和。
这里有一个小观察，就是第一次炸完之后，可以直接往上下左右移动一个格子，这样就可以直接收集了，所以实际被炸掉的只有第一次的，因此只需要用二维前缀和求出第一次炸掉的最少值就可以了。
这道题蠢了，参考了题解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<char>> ma(n, vector<char>(m));
rep(i, 0, n - 1) { rep(j, 0, m - 1) cin >> ma[i][j]; }
int ans = INT_MAX;
vvi pre(n + 1, vi(m + 1));
rep(i, 0, n - 1) { rep(j, 0, m - 1) pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + (ma[i][j] == 'g'); }
auto get = [&](int x1, int y1, int x2, int y2) -> int {
x1 = max(x1, 0);
y1 = max(y1, 0);
x2 = min(x2, n - 1);
y2 = min(y2, m - 1);
if (x1 > x2 || y1 > y2) return 0;
return pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1];
};
rep(i, 0, n - 1) {
rep(j, 0, m - 1) {
if (ma[i][j] != '.') continue;
int x1 = i - k + 1, y1 = j - k + 1;
int x2 = i + k - 1, y2 = j + k - 1;
int cur = get(x1, y1, x2, y2);
ans = min(ans, cur);
}
}
cout << pre[n][m] - ans << endl;
return;
}
|
Minimizing the Sum
出处：CF1969C
题目大意：给定一个数组 $a$ ，现在可以用一个元素的周围元素替换它，最多替换 $k$ 次，问整个数组的最小和是多少？
数据范围： $1 \leq n \leq 3 \cdot 10^5,0 \leq k \leq 10$
思路：这个 $k$ 这么小，一看就可以成为二维DP的一维，因此考虑 $dp[i][j]$ 为前 $i$ 个元素使用了 $j$ 次操作表示的最小值，又考虑这是连着的，因此转移方程就不难推出了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void solve() {
int n, k;
cin >> n >> k;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vvl dp(n + 1, vl(k + 1, LLONG_MAX / 3));
dp[0][0] = 0;
ll ans = LLONG_MAX;
rep(i, 1, n) {
rep(j, 0, k) dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i - 1]);
rep(j, 1, k) {
ll mixx = a[i - 1];
for (int l = 2; l <= j + 1 && l <= i; l++) {
mixx = min(mixx, a[i - l]);
dp[i][j] = min(dp[i][j], dp[i - l][j - (l - 1)] + l * mixx);
}
}
if (i == n) {
rep(j, 0, k) ans = min(ans, dp[i][j]);
}
}
cout << ans << endl;
return;
}
|
Array Painting
出处：CF1849D
题目大意：给定一个 $n$ 个整数组成的数组，每个整数是0,1,2之间的其中一个，起初每个元素都是蓝色的。
现在，需要把每个元素都染成红色，可以执行两种类型的操作，一种是支付一枚硬币，选择一个蓝色元素并染成红色，另一种是选择一个不等于0的红色元素以及跟它相邻的蓝色元素，将所选的红色元素减少1，并将所选的蓝色元素涂成红色。
问一共最少要花费多少硬币？
数据范围： $1 \leq n \leq 2 \cdot 10^5$
思路：首先容易观察到的就是，这题需要按照为0的界限，给连续块分类，否则不能做了。
然后，如果连续块中最大值为1，则可以向两边拓展一个元素，如果最大值为2，那么可以向两边扩展两个元素，于是采用分组循环。
分类后发现，一般的最优策略是向左拓展，但是如果最大值为1的左边没有东西或者左边已经被染了，那么向右拓展，不难的题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
int l = -1, r = -1, maxx = 0;
vector<tri> ma;
rep(i, 0, n - 1) {
if (a[i] == 0) {
if (maxx == 0) continue;
ma.emplace_back(l, i - 1, maxx);
maxx = 0;
l = -1;
} else {
if (l == -1) l = i;
maxx = max(maxx, a[i]);
r = i;
}
}
if (maxx != 0) {
ma.emplace_back(l, r, maxx);
}
int m = sz(ma);
rep(i, 0, m - 1) {
auto& [l, r, maxx] = ma[i];
if (maxx == 1) {
if (l != 0 && a[l - 1] == 0)
a[l - 1] = 1;
else {
if (r != n - 1) a[r + 1] = 1;
}
} else {
if (l != 0) a[l - 1] = 1;
if (r != n - 1) a[r + 1] = 1;
}
}
int ans = m;
rep(i, 0, n - 1) {
if (!a[i]) ans++;
}
cout << ans << endl;
return;
}
|
Doremy’s Connecting Plan
出处：CF1890D
题目大意：现在给定 $n$ 个点，每个点的权值为 $a_i(1 \leq i \leq n)$ ，要连接两个点 $a_i,a_j$ ，当且仅当 $\sum\limits_{i所在联通块}a_k+\sum\limits_{j所在联通块}a_l \geq i \cdot j \cdot c$ ，其中 $c$ 是给定常数，问整个图能否连通。
数据范围： $1 \leq c \leq 10^6,2 \leq n \leq 2 \cdot 10^5,1 \leq a_i \leq 10^{12}$
思路：首先观察到，在两个联通块中，肯定是取它们之间的最小值，收益最大。
然后给出以下观察，每个点都应该连 $a_1$ ，才能最好地连上。
为什么？假设有 $a_i,a_j$ ，它们不能连上 $a_1$ ，但是可以互联，则有：
$$
a_i+a_j \geq i \cdot j \cdot c \\
a_1+a_j < i \cdot c \\
a_1+a_i < j \cdot c \\
$$
将上面式子相加即可推出矛盾。
然后，式子化简为 $sum+a_i \geq i \cdot c$ ，于是可以按照 $sum \geq c \cdot i-a_i$ 来排序，这样就可以更好地贪心实现操作顺序的调度。
一开始一直在想并查集来着。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void solve() {
ll n, c;
cin >> n >> c;
vector<pll> a(n);
rep(i, 0, n - 1) cin >> a[i].first, a[i].second = i + 1;
ll ans = a[0].first;
int tem = 1;
sort(all(a), [&](const pll& x, const pll& y) { return x.first - c * x.second >= y.first - c * y.second; });
rep(i, 0, n - 1) {
if (a[i].second == 1) continue;
if (a[i].first < c * a[i].second - ans) {
cout << "No" << endl;
return;
}
ans += a[i].first;
}
cout << "Yes" << endl;
return;
}
|
Ones and Twos
出处：CF1896D
题目大意：给定一个长度为 $n$ 的数组 $a$ ，其中的元素只有 $1$ 和 $2$ ，现在给定 $q$ 个查询，查询一询问是否存在 $a$ 的子数组，使得其总和等于 $s$ ，查询二将 $a_i$ 修改为 $v$ 。
数据范围： $1 \leq n,q \leq 10^5,1 \leq sum(n+q) \leq 10^5$ 。
思路：这道题一看没啥思路，就说明不是通常套路的，而应该是观察一些性质。
这里注意到，只有存在某个子数组的值为 $x$ ，那么必然存在值为 $x-2$ 的子数组（这个不难验证）。
于是，只需要找出奇偶性的最大和子数组即可，一个是整个数组，另一个只需要维护最左和最右的1即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
void solve() {
int n, op, x, y, q;
cin >> n >> q;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
set<int> s;
int ans = 0;
rep(i, 0, n - 1) {
if (a[i] == 1) s.insert(i);
ans += a[i];
}
rep(i, 0, q - 1) {
cin >> op;
if (op == 1) {
cin >> x;
if (x > ans) {
cout << "NO" << endl;
continue;
}
if (ans % 2 == x % 2) {
cout << "YES" << endl;
continue;
}
if (s.empty()) {
cout << "NO" << endl;
continue;
}
int tem = *s.begin();
int tem2 = *(--s.end());
int maxx = max(ans - 2 * tem - 1, ans - 2 * (n - 1 - tem2) - 1);
if (maxx >= x) {
cout << "YES" << endl;
} else
cout << "NO" << endl;
} else {
cin >> x >> y;
ans -= a[x - 1];
ans += y;
a[x - 1] = y;
if (y != 1 && s.count(x - 1))
s.erase(x - 1);
else if (y == 1 && !s.count(x - 1))
s.insert(x - 1);
}
}
return;
}
|
Mad City
出处：CF1873H
题目大意：Alice和Bob在一个有 $n$ 个点， $n$ 条边的图中，Alice想抓住Bob，但是Bob知道她的所有行动，因此可以对应调整策略，现在Alice从 $a$ 出发，Bob从 $b$ 出发，问Bob是否能在所有Alice的策略下，都能不被抓到？
数据范围： $3 \leq n \leq 2 \cdot 10^5, 1 \leq u_i,v_i \leq n$
思路：首先看到这里，图中必然有一个环，从而如果Bob在这个环里，那么啥事都没有，如果不在的话，如果Alice能进来堵他进入这个环，那么会被抓到，否则等Bob进环了，还是啥事都没有。
但是，找环的算法要复习一下，就是BFS，不断去除叶子，剩下的就是环了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
void solve() {
int n, a, b, x, y;
cin >> n >> a >> b;
a--;
b--;
vvi ma(n);
vi deg(n);
rep(i, 0, n - 1) {
cin >> x >> y;
ma[x - 1].push_back(y - 1);
ma[y - 1].push_back(x - 1);
deg[x - 1]++;
deg[y - 1]++;
}
if (a == b) {
cout << "NO" << endl;
return;
}
queue<int> q;
vector<bool> vis(n, false);
rep(i, 0, n - 1) {
if (deg[i] == 1) q.push(i);
}
while (!q.empty()) {
auto node = q.front();
q.pop();
vis[node] = true;
for (int& p : ma[node]) {
if (--deg[p] == 1) q.push(p);
}
}
if (!vis[b]) {
cout << "YES" << endl;
return;
}
vi cir;
rep(i, 0, n - 1) {
if (!vis[i]) cir.push_back(i);
}
vi dis1(n, -1);
vi dis2(n, -1);
auto bfs = [&](int x, vi& d) -> void {
queue<int> q;
q.push(x);
d[x] = 0;
while (!q.empty()) {
auto node = q.front();
q.pop();
for (int& p : ma[node]) {
if (d[p] < 0) {
d[p] = d[node] + 1;
q.push(p);
}
}
}
return;
};
bfs(a, dis1);
bfs(b, dis2);
int mixx = INT_MAX, idx = -1;
int m = sz(cir);
rep(i, 0, m - 1) {
if (dis2[cir[i]] < mixx) {
mixx = dis2[cir[i]];
idx = cir[i];
}
}
if (dis1[idx] <= mixx)
cout << "NO" << endl;
else
cout << "YES" << endl;
return;
}
|
Climbing the Tree
出处：CF1810D
题目大意：蜗牛正在爬树，每天早上爬 $a$ 米，晚上掉下来 $b$ 米，你不知道树的高度，现在有 $q$ 个时间，事件有两种，事件一是一只蜗牛给定它的 $a,b$ ，并说爬了 $n$ 天，如果是真的，那么采用它的信息，如果是假的请报告；事件二是一只给定 $a,b$ 的蜗牛，如果在当前信息下能给出唯一的天数，那么输出，如果不行请报告。
数据范围： $1 \leq q \leq 2 \cdot 10^5,1 \leq a,b,n \leq 10^9,a > b$ 。
思路：很显然的合并区间问题，感觉不是很想说，小学奥数吧，时间复杂度为 $O(q)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
void solve() {
int q, op;
ll a, b, n;
cin >> q;
ll l = -1, r = LLONG_MAX;
rep(t, 0, q - 1) {
cin >> op;
if (op == 1) {
cin >> a >> b >> n;
ll l1, r1;
r1 = (a - b) * (n - 1) + a;
if (n == 1)
l1 = 1;
else
l1 = max((a - b) * (n - 2) + a + 1, (a - b) * (n - 1) + 1);
if (r1 < l || l1 > r) {
cout << 0 << ' ';
continue;
}
l = max(l, l1);
r = min(r, r1);
cout << 1 << ' ';
} else {
cin >> a >> b;
if (l == -1) {
cout << -1 << ' ';
continue;
}
ll ans_1 = (l <= a) ? 1 : (l - a - 1) / (a - b) + 2;
ll ans_2 = (r <= a) ? 1 : (r - a - 1) / (a - b) + 2;
if (ans_1 == ans_2)
cout << ans_1 << ' ';
else
cout << -1 << ' ';
}
}
cout << endl;
return;
}
|
SlavicG’s Favorite Problem
出处：CF1760G
题目大意：给定一棵 $n$ 个节点的树，每条边都有一个权值，现在要从 $a$ 出发到 $b$ ，但是要求到达 $b$ 的时候走过的边异或值为0，同时不能先到 $b$ 走一段再折回去。
同时，可以使用一次传送机会，可以从任意地点传送到非 $b$ 的地方，问是否能到 $b$ ？
数据范围： $2 \leq n \leq 10^5,1 \leq w_i \leq 10^9$
思路：很容易的前后缀分解和枚举右维护左思想，只需要跑两遍DFS，求出两个点到各个点的异或路径值，并用哈希表存一下跑跑即可，需要注意的是，由于不能先穿过 $b$ ，因此跑 $a$ 点的时候需要特判一下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
void solve() {
int n, a, b, x, y, z;
cin >> n >> a >> b;
a--;
b--;
vector<vector<pii>> ma(n);
rep(i, 1, n - 1) {
cin >> x >> y >> z;
ma[x - 1].emplace_back(y - 1, z);
ma[y - 1].emplace_back(x - 1, z);
}
vi d1(n, -1);
vi d2(n);
auto dfs = [&](this auto&& dfs, int x, int pa, int t) -> void {
d1[x] = t;
for (auto& [p, v] : ma[x]) {
if (p == pa || p == b) continue;
dfs(p, x, t ^ v);
}
return;
};
dfs(a, -1, 0);
auto dfs2 = [&](this auto&& dfs2, int x, int pa, int t) -> void {
d2[x] = t;
for (auto& [p, v] : ma[x]) {
if (p == pa) continue;
dfs2(p, x, t ^ v);
}
};
dfs2(b, -1, 0);
map<int, int> ma2;
rep(i, 0, n - 1) {
if (i == b) continue;
ma2[d2[i]]++;
}
rep(i, 0, n - 1) {
if (d1[i] != -1 && ma2.count(d1[i])) {
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
return;
}
|
Long Beautiful Integer
出处：CF1268A
题目大意：给定一个由 $a_1,\ldots,a_n$ 从左到右构成的整数 $x$ 和一个正整数 $k$ ，若由 $b_1,b_2,\ldots,b_m$ 从左到右构成的整数满足 $\forall i \in [1,m-k],b_i=b_{i+k}$ ，则称其为美丽数，请求出最小的美丽数 $y$ ，使得 $y \geq x$ 。
数据范围： $2 \leq n \leq 200000$
思路：考虑 $a$ 的前 $k$ 个数，求出如果它使用原来的数，后续是先被大于还是先被小于，并保留大于跟小于的位置，然后考虑是否需要处理当前的数，如果需要处理，找到第一个需要处理的位置，后续全部置0，感觉corner case比较多。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
void solve() {
int n, k;
cin >> n >> k;
string s;
cin >> s;
vi a(n);
rep(i, 0, n - 1) a[i] = s[i] - '0';
vi b(n);
vi tem(k);
vi tem2(k);
rep(i, 0, k - 1) {
int pd = 0;
int idx = -1;
for (int j = i; j <= n - 1; j += k) {
if (a[j] > a[i]) {
pd = 1;
idx = j;
break;
} else if (a[j] < a[i]) {
pd = 2;
idx = j;
break;
}
}
tem[i] = pd;
tem2[i] = idx;
}
bool flag = false;
frep(i, k - 1, 0) {
if (tem[i] == 1) {
flag = true;
break;
}
}
int idx = INT_MAX;
rep(i, 0, k - 1) {
if (tem[i] == 1) {
idx = min(idx, tem2[i]);
}
}
int idx2 = INT_MAX;
rep(i, 0, k - 1) {
if (tem[i] == 2) {
idx2 = min(idx2, tem2[i]);
}
}
bool flag2 = (idx < idx2);
if (flag && flag2) {
frep(i, k - 1, 0) {
if (a[i] != 9) {
a[i]++;
rep(j, i + 1, k - 1) a[j] = 0;
break;
}
}
}
cout << n << endl;
rep(i, 0, n - 1) cout << a[i % k];
cout << endl;
return;
}
|
Omkar and Bed Wars
出处：CF1392D
题目大意：给定一个环形队列，和一个字符串，$s_i$ 为 $L$ 表示这个玩家攻击他左边的玩家， $s_i$ 为 $R$ 表示这个玩家攻击他右边的玩家，现在需要执行以下策略：如果某个玩家正在被一个其他玩家攻击，那么他要反击，如果被0或2个玩家攻击，那么他可以合理地攻击任意一个相邻玩家。
现在需要修改 $S$ 以符合以上策略，问最少需要修改的位置数？
数据范围： $3 \leq n \leq 2 \cdot 10^5$
思路：注意到若存在不合法的攻击状态，则必然存在连续三个人的攻击方向相同，于是考虑分段处理，再手玩样例发现如果全部都为 $R$ 或者 $L$ 时需要特判，然后贪心即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
void solve() {
int n;
cin >> n;
string s;
cin >> s;
rep(i, 0, n - 1) s.push_back(s[i]);
int idx = -1;
rep(i, 1, n - 1) {
if (s[i] != s[i - 1]) {
idx = i;
break;
}
}
if (idx == -1) {
cout << (n + 2) / 3 << endl;
return;
}
int ans = 0;
int tem = 0;
rep(i, idx, idx + n - 1) {
if (i == idx || s[i] != s[i - 1]) {
ans += tem / 3;
tem = 1;
} else
tem++;
}
if (tem) ans += tem / 3;
cout << ans << endl;
return;
}
|
MEX and Increments
出处：CF1619E
题目大意：有一个包含 $n$ 个非负元素的数组 $a_1,a_2,\ldots,a_n$ ，每次操作可以选择任意一个下标 $j$ ，并将 $a_j=a_j+1$ ，对于每个 $i$ 从 $0$ 到 $n$ ，问是否可以通过若干次操作使得数组的MEX值恰好为 $i$ ，若可以，请输出最小操作数。
数据范围： $1 \leq n \leq 2 \cdot 10^5$
思路：考虑顺序遍历，思考，如果 $MEX(a)=i$ 可行，那么什么情况下 $MEX(a)=i+1$ 可行？首先考虑，如果当前存着 $i+1$ ，那么必然要把它们全部先驱逐到 $i+2$ 中，于是得到答案，同时根据贪心，还需要把之前最近的一个剩余的数，加到 $i-1$ 。如果没有存的话，那么还是把之前最近的一个剩余的数，加到 $i-1$ ，或者看有没有存 $i-1$ ，由于涉及大小关系，可以用栈的FIFO管理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ranges::sort(a);
vl res(n + 1, -1);
bool flag = true;
map<ll, ll> ma;
rep(i, 0, n - 1) ma[a[i]]++;
stack<ll> st;
ll tem = 0;
if (a[0] != 0) {
res[0] = 0;
for (auto& p : res) cout << p << ' ';
cout << endl;
return;
}
rep(i, 0, n) {
if (ma.count(i)) {
if (i >= 1 && !ma.count(i - 1)) {
if (st.empty()) break;
auto node = st.top();
st.pop();
tem += 1LL * i - 1LL - 1LL * node;
ma[node]--;
ma[i - 1]++;
}
rep(j, 1, ma[i] - 1) st.push(i);
res[i] = tem + ma[i];
} else {
if (ma.count(i - 1))
res[i] = tem;
else {
if (st.empty()) break;
auto node = st.top();
st.pop();
tem += 1LL * i - 1LL - node;
res[i] = tem;
ma[node]--;
ma[i - 1]++;
}
}
}
for (auto& p : res) cout << p << ' ';
cout << endl;
return;
}
|
Train Splitting
出处：CF1776F
题目大意：给定一个 $n$ 个点 $m$ 条边的无向图，现在将把所有边染成 $k$ 中颜色的其中一种，需要满足以下条件：对于任意一种颜色，存在两个城市，它们之间仅由这种颜色的边互相不可达；同时对于任意两种颜色，所有城市都可以通过这两种颜色的边互相可达，请构造一种解决方案，注意不需要最大化或者最小化 $k$ 。
数据范围： $3 \leq n \leq 50, n-1 \leq m \leq \frac{n(n-1)}{2}$
思路：注意到可以用一个颜色的边将某个点完全分离开（如果 $deg(i) < n$ ），于是对于一般图只需要采用两种颜色的边即可，而当其为完全图时，则需要多添加一种颜色，这就做完了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
void solve() {
int n, m, x, y;
cin >> n >> m;
vvi ma(n);
vi deg(n);
vi res(m, 2);
rep(i, 0, m - 1) {
cin >> x >> y;
ma[x - 1].push_back(i);
ma[y - 1].push_back(i);
deg[x - 1]++, deg[y - 1]++;
}
if (m == n * (n - 1) / 2) {
rep(i, 0, n - 2) { res[ma[0][i]] = 1; }
res[ma[0][0]] = 3;
cout << 3 << endl;
} else {
int idx = -1;
rep(i, 0, n - 1) {
if (deg[i] != n - 1) {
idx = i;
break;
}
}
rep(i, 0, sz(ma[idx]) - 1) res[ma[idx][i]] = 1;
cout << 2 << endl;
}
rep(i, 0, m - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
Yet Another Tournament
出处：CF1783C
题目大意：现在有 $n+1$ 名参赛者，你是其中一个，给定 $a_1 \ldots a_n$ ，你需要至少准备 $a_i$ 分钟，才能战胜他，但是总的准备时间只有 $m$ 分钟，对于他们自己而言，如果 $i < j$ ，那么 $j$ 就战胜了 $i$ ，请给出你的最小可能名次。
数据范围： $1 \leq n \leq 5 \cdot 10^5$
思路：注意到每个人能赢的场数是固定的，因此还是应该尽可能赢更多的场。
假设当前最多能赢 $k$ 场，那么考虑赢 $k+1$ 场的人，如果赢下他，那么我们的名字就能上升一名了，做个特判即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
void solve() {
int n, m;
cin >> n >> m;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
auto b = a;
ranges::sort(b);
int k = 0;
int tem = 0;
rep(i, 0, n - 1) {
if (tem + b[i] > m) break;
tem += b[i];
k++;
}
if (k == n) {
cout << 1 << endl;
return;
}
if (k == 0) {
cout << n + 1 << endl;
return;
}
if (tem - b[k - 1] + a[k] <= m)
cout << n - k << endl;
else
cout << n - k + 1 << endl;
return;
}
|
Magic Triples(Easy)
出处：CF1822G1
题目大意：给定一个长度为 $n$ 的整数序列 $a$ ，如果三元组 $(i,j,k)$ 满足以下条件，就称其为魔法三元组：
- $1 \leq i,j,k \leq n$
- $i,j,k$ 互不相同
- 存在一个正整数 $b$ ，使得 $a_i \cdot b=a_j$ ，且 $a_j \cdot b=a_k$
数据范围： $3 \leq n \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^6$
思路：看到这个 $a_i$ 的值域，很容易想到调和级数，于是考虑枚举起始项，然后调和级数枚举中间项来得到最高项，从而就能做了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
map<ll, int> ma;
rep(i, 0, n - 1) ma[a[i]]++;
ll ans = 0;
for (auto& [x, y] : ma) {
if (y >= 3) ans += 1LL * y * (y - 1) * (y - 2);
}
int maxx = *max_element(all(a));
for (auto& [i, z] : ma) {
for (int j = 2 * i; j <= maxx; j += i) {
if (1LL * j * j / i > maxx) break;
if (ma.count(j) && ma.count(1LL * j * j / i)) {
ans += 1LL * ma[i] * ma[j] * ma[1LL * j * j / i];
}
}
}
cout << ans << endl;
return;
}
|
0,1,2,Tree!
出处：CF1950F
题目大意：请找到有 $a+b+c$ 个节点的最小有根树高度，其中有 $a$ 个节点有两个孩子， $b$ 个节点有一个孩子， $c$ 个节点有 $0$ 个孩子。
数据范围： $0 \leq a,b,c \leq 10^5,1 \leq a+b+c \leq 3 \cdot 10^5$
思路：注意到贪心做法是先让二叉节点铺满，再铺一叉节点即可，这题不难，而特判也只需要判断一下握手定理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void solve() {
int a, b, c;
cin >> a >> b >> c;
int n = a + b + c;
if (n - 1 != 2 * a + b) {
cout << -1 << endl;
return;
}
if (a == 0) {
cout << b << endl;
return;
}
int tem = __lg(a) + 1;
int tem2 = (1 << tem) - 1;
if (b <= tem2 - a) {
cout << tem << endl;
return;
}
b -= (tem2 - a);
int tem3 = (1 << tem) - (tem2 - a);
tem += (b + tem3 - 1) / tem3;
cout << tem << endl;
return;
}
|
Minimize Fixed Points
出处：CF2123F
题目大意：称一个长度为 $n$ 的排列为好的，当且仅当对 $2 \leq i \leq n,gcd(p_i,i) > 1$ ，请在所有的好排列中，找到不定点最少的好排列。
数据范围： $2 \leq n \leq 10^5$
思路：显然 $a_1=1$ 。
首先考虑的是，对于某个质数，对他的所有倍数做一下shift，从而得到最后结果。
试了之后发现，为了保证每个数只被shift一次，因此考虑使用最小素因子进行shift。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
constexpr int MX = 1e5 + 1;
bool pd[MX];
vi primes;
int minp[MX];
auto init = [] {
rep(i, 2, MX - 1) {
if (!pd[i]) {
primes.push_back(i);
minp[i] = i;
}
for (int& p : primes) {
if (1LL * p * i >= MX) break;
pd[i * p] = true;
minp[i * p] = max(minp[i], p);
if (i % p == 0) break;
}
}
return 0;
}();
void solve() {
int n;
cin >> n;
vi a(n + 1);
a[1] = 1;
int cnt = 0;
map<int, vi> ma;
rep(i, 2, n) { ma[minp[i]].push_back(i); }
for (auto& [x, y] : ma) {
int m = sz(y);
rep(i, 0, m - 1) { a[y[(i + 1) % m]] = y[i]; }
}
rep(i, 1, n) cout << a[i] << ' ';
cout << endl;
}
|
Riverside Curio
出处：CF924C
题目大意：给定 $a_1,\ldots,a_n$ ，$a_i$ 表示第 $i$ 天在水位上方的标记数，每天需要标记当天的水位标记，如果已经存在标记了，则不会再新建标记，定义 $d_i$ 为第 $i$ 天水位下方的标记数，请求出 $\sum\limits_{i=1}^{n}d_i$ 的最小值。
数据范围： $1 \leq n \leq 10^5,0 \leq a_i < i$
思路：注意到只需要求出当天的最少刻线数，而这个刻线数是受到两边压制的。
于是考虑正反跑两遍，先反着跑求出当天的下界，再正着跑求出当天的下界，最后求个总和就做完了。
这题参考了题解，思路很edu。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll mixx = LLONG_MAX;
ll ans = 0;
vl suf(n);
suf[n - 1] = a[n - 1];
frep(i, n - 2, 0) { suf[i] = max(suf[i + 1] - 1, a[i]); }
rep(i, 1, n - 1) suf[i] = max(suf[i - 1], suf[i]);
rep(i, 0, n - 1) { ans += 1LL * (suf[i] - a[i]); }
cout << ans << endl;
return;
}
|
