B
题目大意：Steve 和其他 $n$ 个村民一起生活在一个村庄里。不幸的是，由于对祖母绿分配的争执，这些村民之间没有任何人是朋友。此外，第 $i$ 个村民初始的暴躁值为 $g_i$。Steve 可以进行如下操作任意多次： - 选择两个村民 $i$ 和 $j$，给他们 $\max(g_i, g_j)$ 颗祖母绿让他们分享。两人的暴躁值都会减少 $\min(g_i, g_j)$，如果他们还不是朋友，则他们会成为朋友。Steve 希望让每个村民都能通过一系列朋友关系与其他所有村民连通。也就是说，从任意一个村民出发，都可以通过朋友关系链到达任意其他村民。由于他不想让村庄的经济膨胀太多，需要计算他至少需要送出多少颗祖母绿才能实现目标。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \cdot 10^5$，$1 \le g_i \le 10^9$，$\sum n \le 2 \cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
sort(all2(a));
ll ans = 0;
if (n % 2 == 0) {
for (int i = 0; i <= n - 1; i += 2) ans += max(a[i], a[i + 1]);
} else {
for (int i = 0; i < n - 1; i += 2) ans += max(a[i], a[i + 1]);
ans += a[n - 1];
}
cout << ans << endl;
return;
}
|
C
题目大意：这是一个交互题。Steve 最近发现了下界（The Nether），他在自己的世界里建造了 $n$ 个下界传送门，每个传送门的位置都不同。每个传送门都以有向的方式连接到若干（可能为零）其他传送门。为了避免迷路，Steve 精心设计了传送门网络，使得不存在通过一系列传送门跳跃后又回到原位置的情况；形式上，这个网络构成了一个有向无环图（DAG）。Steve 不会告诉你哪些传送门彼此相连，但他允许你进行询问。
数据范围：$1 \le t \le 1000$，$2 \le n \le 500$。
思路：
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
| using i128 = __int128_t;
ll ask(ll x, ll k, vl& res) {
cout << "? " << x << ' ' << k << ' ';
rep(i, 0, sz(res) - 1) cout << res[i] << ' ';
cout << '\n';
cout.flush();
ll op;
cin >> op;
return op;
}
void report(ll k, vl& res) {
cout << "! " << k << ' ';
rep(i, 0, sz(res) - 1) cout << res[i] << ' ';
cout << '\n';
cout.flush();
}
void solve() {
ll n;
cin >> n;
vl res(n + 1);
vl tem;
rep(i, 1, n) tem.push_back(i);
rep(i, 1, n) res[i] = ask(i, n, tem);
int idx = -1;
ll maxx = LLONG_MIN;
rep(i, 1, n) {
if (res[i] > maxx) {
maxx = res[i];
idx = i;
}
}
vl res2;
map<ll, vl> ma;
rep(i, 1, n) { ma[res[i]].push_back(i); }
res2.push_back(idx);
while (res[idx] > 1) {
ll tem2 = -1;
for (auto& p : ma[res[idx] - 1]) {
vl tem3;
tem3.push_back(p);
tem3.push_back(idx);
ll op = ask(idx, 2, tem3);
if (op == 2) {
tem2 = p;
break;
}
}
res2.push_back(tem2);
idx = tem2;
}
report(sz(res2), res2);
return;
}
|
D
题目大意：Steve 面对一个由 $n$ 个生物从下到上叠成的 chicken jockey，第 $i$ 个生物初始生命值为 $h_i$。每次攻击可造成 $1$ 点伤害，生物死亡后上方生物会下落并受到额外伤害。求消灭整叠生物所需的最少攻击次数。
数据范围：$1 \le t \le 10^4$，$2 \le n \le 2 \times 10^5$，$1 \le h_i \le 10^9$，$\sum n \le 2 \times 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
| using i128 = __int128_t;
void solve() {
ll n;
cin >> n;
vl a(n + 1);
rep(i, 1, n) cin >> a[i];
vl dp(n + 1);
dp[1] = a[1];
rep(i, 2, n) { dp[i] = min(dp[i - 1] + a[i] - 1, dp[i - 2] + max(0LL, a[i] - (i - 1)) + a[i - 1]); }
cout << dp[n] << endl;
return;
}
|
