B
题目大意：Alice 和 Bob 玩一个游戏，Alice 给 Bob 一个正整数 $x \le 10^8$。为了赢得游戏，Bob 需要找到另一个正整数 $y \le 10^9$，使得 $x \operatorname{\#} y$ 能被 $x + y$ 整除。这里 $x\operatorname{\#}y$ 表示将整数 $x$ 和 $y$ 按顺序拼接形成的新整数。然而，由于 Bob 太笨，无法找到这样的整数。需要帮助他。可以证明，满足条件的整数 $y$ 总是存在。
数据范围：$1 \le t \le 10^4$，$1 \le x \le 10^8$。
思路：
1
2
3
4
5
6
7
| using i128 = __int128_t;
void solve() {
ll x;
cin >> x;
cout << 2 * x << endl;
return;
}
|
C
题目大意：给定数组 $a$，定义函数 $f(a)$ 为操作代价加上数组的交错和。Alice 与 Bob 轮流在数组上进行操作或终止游戏，双方最优时需要求最终的函数值。
数据范围：$1 \le t \le 10^4$，$1 \le n \le 2\cdot10^5$，$1 \le a_i \le 10^9$，$\sum n \le 2\cdot10^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
29
30
31
32
33
34
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
ll ans = 0;
rep(i, 0, n - 1) {
if (i % 2 == 0)
ans += a[i];
else
ans -= a[i];
}
ll ans2 = ans;
ans2 = max(ans2, ans + (n % 2 == 0 ? n - 2 : n - 1));
set<ll> tem;
rep(i, 0, n - 1) {
if (i % 2 == 1)
tem.insert(2 * a[i] - i);
else {
if (!tem.empty()) ans2 = max(ans2, ans + *prev(tem.end()) - (2 * a[i] - i));
}
}
tem.clear();
rep(i, 0, n - 1) {
if (i % 2 == 1) {
if (!tem.empty()) ans2 = max(ans2, ans + 2 * a[i] + i - *tem.begin());
} else {
tem.insert(2 * a[i] + i);
}
}
cout << ans2 << endl;
return;
}
|
D
题目大意：给你 $n$ 个在数轴上的线段，第 $i$ 条线段表示为 $[l_i, r_i]$。初始时，所有线段都是未标记的。你将不断重复以下操作，直到没有未标记的线段为止： 1. 在第 $k$ 次操作中，如果目前有至少两条未标记的线段，任选两条未标记的线段 $[l_i, r_i]$ 和 $[l_j, r_j]$，将这两条线段都标记，并新增一条满足以下条件的标记线段 $[x_k, y_k]$： - $l_i \leq x_k \leq r_i$， - $l_j \leq y_k \leq r_j$， - $x_k \leq y_k$。2. 如果只剩一条未标记的线段，则将其标记。需要求出执行完所有操作后，所有标记线段的长度之和的最大可能值。
数据范围：$1 \le t \le 10^4$，$1 \leq n \leq 2 \times 10^5$，$1 \leq l_i \leq r_i \leq 10^9$，$\sum n \le 2 \times 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
29
30
31
32
33
34
35
36
37
38
39
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vector<pll> ma(n);
rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
if (n == 1) {
cout << ma[0].second - ma[0].first << endl;
return;
}
ll ans = 0;
rep(i, 0, n - 1) ans += ma[i].second - ma[i].first;
sort(all(ma), [&](const pll& x, const pll& y) { return x.first + x.second < y.first + y.second; });
if (n % 2 == 0) {
ll l = 0, r = n - 1;
while (l < r) {
ans += ma[r].second - ma[l].first;
l++, r--;
}
cout << ans << endl;
return;
}
vl pre1(n);
vl pre2(n);
pre1[0] = ma[0].first, pre2[n - 1] = ma[n - 1].second;
rep(i, 1, n - 1) pre1[i] = pre1[i - 1] + ma[i].first;
rep(i, 1, n - 1) pre2[i] = pre2[i - 1] + ma[i].second;
ll ans2 = ans;
rep(i, 0, n - 1) {
if (i < n / 2)
ans2 = max(ans2, ans + pre2[n - 1] - pre2[n / 2] - pre1[n / 2] + ma[i].first);
else if (i == n / 2)
ans2 = max(ans2, ans + pre2[n - 1] - pre2[n / 2] - pre1[n / 2 - 1]);
else
ans2 = max(ans2, ans + pre2[n - 1] - pre2[n / 2 - 1] - pre1[n / 2 - 1] - ma[i].second);
}
cout << ans2 << endl;
return;
}
|
