比赛链接
感觉太久没打 Codeforces 了，感觉打得一坨屎啊。
还把第二天的课翘了，还他妈的恰好点名，懒得喷。
A. Shift Sort
给定一个长度为 $n$ 的 01 序列，可以任选一个三元组 $1 \le i \lt j \lt j \le n$ 然后让这个三元组内的元素循环左移或右移，问多少次操作可以使得这个 01 序列变得有序。
妈的，差点卡签到了。
我们考虑三元组 $(1, 0, 0)$ 我们可以把它变成 $(0, 1, 1)$，然后我们再考虑 $(1, 1, 0)$，我们可以把它变成 $(0, 1, 1)$，总之，我们可以发现对于任意的不在位置上的字符，我们总是可以通过一次操作把它放好。因此答案就是 $0$ 的个数 $\mathrm{cnt}$ 减去前 $\mathrm{cnt}$ 个元素中 $1$ 的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void solve() {
int n;
cin >> n;
string s;
cin >> s;
int c0 = 0;
for (int i = 0; i < n; i++)
if (s[i] == '0')
c0++;
int c1 = 0;
for (int i = 0; i < c0; i++) {
if (s[i] == '1')
c1++;
}
cout << c1 << "\n";
}
|
B. Another Divisibility Problem
我们定义 $x \# y = x \times 10^{\log_{10}{y} + 1} + y$，然后给定 $x$ 求 $y$ 使得 $(x + y) \mid (x \# y)$。
感觉比 A 简单。
不难发现因为 $x \# y = x \times 10^{\log_{10}{y} + 1} + y = x \times (10^{\log_{10}{y} + 1} - 1) + (x + y)$，显然我们很讨厌 $x$ 的幂次的那一坨东西，我们尝试固定 $y$ 的位数，这里考虑 $x \lt 10^8$ 因此取 $y=10^9-1-x$，此时原式转化为 $x \times (10^9 - 1) + (x+y)$，然后我们考虑 $x + y = 10^9 - 1$，显然成立。
1
2
3
4
5
6
| void solve() {
int x;
cin >> x;
int res = 1e9 - 1 - x;
cout << res << "\n";
}
|
C. Ultimate Value
唉唉，神秘博弈论。
定义一个作用于长度为 $n$ 的数组 $a$ 的函数 $f(x) = \mathrm{cost} + (a_1-a_2+a_3-a_4+\cdots a_n)$，其中 $\mathrm{cost}$ 的初始值为 $0$。
然后我们有两个人，一个是 Alice 一个是 Bob，两个轮流操作，Alice 先手，每次操作执行一次下列操作之一：
- 结束游戏
- 选择 $l, r(1 \le l \le r \le n)$ 并交换 $a_l$ 和 $a_r$，并在 $\mathrm{cost}$ 中增加 $r-l$。
Alice 希望最大化 $f(a)$，Bob 则反之，问最后的 $f(a)$ 是多少。
首先我们可以发现这个游戏中 Bob 饰演无能的丈夫——对于 Bob 所做的任意操作，Alice 都可以在下一回合把这个操作弄回去，顺便增加一下 $\mathrm{cost}$，因此 Bob 在 Alice 第一次操作后立即结束就行。
然后我们模拟一下 Alice 第一次操作的最大值就行。
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 solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int sum = 0;
for (int i = 1; i <= n; i++) {
if (i % 2)
sum += a[i];
else
sum -= a[i];
}
int bst = 0;
int fo, lo, fe, le;
fo = lo = fe = le = -1;
for (int i = 1; i <= n; i++) {
if (i % 2) {
if (fo == -1)
fo = i;
lo = i;
} else {
if (fe == -1)
fe = i;
le = i;
}
}
if (fo != -1 and lo > fo)
bst = max(bst, lo - fo);
if (fe != -1 and le > fe)
bst = max(bst, le - fe);
int mn = INF;
for (int i = 1; i <= n; i++) {
if (i % 2)
mn = min(mn, i + 2 * a[i]);
else {
if (mn < INF) {
bst = max(bst, i + 2 * a[i] - mn);
}
}
}
int nm = INF;
for (int i = 1; i <= n; i++) {
if (i % 2 == 0)
nm = min(nm, i - 2 * a[i]);
else {
bst = max(bst, i - 2 * a[i] - nm);
}
}
cout << sum + max(0ll, bst) << "\n";
}
|
D. A Cruel Segment’s Thesis
ああ、傻逼了一个晚上，唐完了。
给定 $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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
using i3 = array<int, 3>;
void solve() {
int n;
cin >> n;
int ans = n / 2;
vector<pair<int, int>> a(n);
vector<i3> b(n);
for (int i = 0; auto &[l, r] : a) {
cin >> l >> r;
ans += r - l;
b[i++] = {l + r, l, r};
}
sort(b.begin(), b.end());
if (n % 2 == 0) {
for (int i = 0; i < n; i++)
ans += a[i].second;
for (int i = 0; i < n / 2; i++)
ans -= b[i][0];
cout << ans - n / 2 << "\n";
} else {
int k = 0, w = 0;
for (int i = 0; i < n; i++)
w += a[i].second;
for (int i = 0; i < n / 2 + 1; i++)
w -= b[i][0];
for (int i = 0; i < n / 2 + 1; i++)
k = max(k, w + b[i][1]);
w += b[n / 2][0];
for (int i = n / 2 + 1; i < n; i++)
k = max(k, w - b[i][2]);
cout << ans + k - n / 2 << "\n";
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--)
solve();
return 0;
}
|