B
题目大意：Maple 想为 Chocola 和 Vanilla 烤一些蛋糕。有一天，她发现了 $n$ 个魔法蛋糕烤箱。第 $i$ 个烤箱每秒可以烤出 $a_i$ 个蛋糕。这些蛋糕会一直留在各自的烤箱中，直到被收集。在每一秒结束时，她可以传送到任意一个烤箱（包括当前所在的烤箱），并收集该烤箱中至今为止累积的所有蛋糕。需要，求出 Maple 在 $m$ 秒内最多可以收集到多少蛋糕。
数据范围：$1 \le t \le 1000$，$1 \leq n \leq 10^5$，$1 \leq m \leq 10^8$，$1 \leq a_i \leq 10^5$，$\sum n \le 2 \cdot 10^5$。
思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| using i128 = __int128_t;
void solve() {
ll n, m;
cin >> n >> m;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
sort(all2(a));
ll ans = 0;
rep(i, 0, n - 1) {
if (i >= m) break;
ans += a[i] * (m - i);
}
cout << ans << endl;
return;
}
|
C
题目大意：Chocola 和 Vanilla 都喜欢蛋糕。今天，一家蛋糕店的经理送给她们总共 $2^{k+1}$ 个蛋糕。这些蛋糕被平均分配，所以她们每人一开始都收到了 $2^k$ 个蛋糕。然而，Chocola 和 Vanilla 现在想要重新分配蛋糕，使得 Chocola 最终有恰好 $x$ 个蛋糕，Vanilla 拥有剩下的 $2^{k+1}-x$ 个蛋糕。在每一步操作中，她们可以执行以下两种操作之一，且只能选择其中之一： 1. Chocola 把自己的一半蛋糕给 Vanilla。只有当 Chocola 当前蛋糕数为偶数时，这个操作才允许。2. Vanilla 把自己的一半蛋糕给 Chocola。只有当 Vanilla 当前蛋糕数为偶数时，这个操作才允许。
数据范围：$1 \le t \le 1000$，$1 \le k \le 60$，$1 \le x \le 2^{k+1}-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
| using i128 = __int128_t;
void solve() {
ll k, x;
cin >> k >> x;
vl ans;
auto dfs = [&](this auto&& dfs, ll mid) -> void {
if (mid == (1LL << k))
return;
else if (mid < (1LL << k)) {
ans.push_back(1);
dfs(mid * 2);
} else {
ans.push_back(2);
dfs(2 * mid - (1LL << (k + 1)));
}
return;
};
dfs(x);
ranges::reverse(ans);
cout << sz(ans) << endl;
for (auto& p : ans) cout << p << ' ';
cout << endl;
return;
}
|
D
题目大意：对于长度为 $m$ 的数组 $b$，你可以进行以下两种操作： 1. 选择一个下标 $1\le i\le m-1$，然后交换 $b_i$ 和 $b_{i+1}$ 的值。2. 选择一个下标 $1\le i\le m-2$，然后交换 $b_i$ 和 $b_{i+2}$ 的值。但是，你至多只能执行一次操作 $2$。我们定义 $f(b)$ 表示将数组 $b$ 通过这两种操作排序为非递减序列所需的最小操作次数，$g(b)$ 表示只使用操作 $1$（相邻交换）将数组 $b$ 排序为非递减序列所需的最小操作次数。如果对每个 $b$ 都有 $f(b) = g(b)$，那么这个数组 $b$ 被称为“完美的”（即 perfect）。
数据范围：$1\le t\le 5\times10^4$，$1\le n, q\le 5\times 10^5$，$1\le a_i \le n$，$1\le l\le r\le n$，$\sum n \le 5\times 10^5$，$\sum q \le 5\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
| using i128 = __int128_t;
void solve() {
ll n, q, x, y;
cin >> n >> q;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
vector<int> r(n, n);
vector<int> l(n, -1);
stack<int> s;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && a[s.top()] >= a[i]) s.pop();
if (!s.empty()) r[i] = s.top();
s.push(i);
} // 求右边第一个小于的下标
while (!s.empty()) s.pop();
for (int i = 0; i <= n - 1; i++) {
while (!s.empty() && a[s.top()] <= a[i]) s.pop();
if (!s.empty()) l[i] = s.top();
s.push(i);
} // 求左边第一个小于的下标
vi pre(n, INT_MAX);
rep(i, 0, n - 1) {
if (l[i] != -1 && r[i] != n) pre[l[i]] = min(pre[l[i]], r[i]);
}
frep(i, n - 2, 0) pre[i] = min(pre[i + 1], pre[i]);
rep(i, 0, q - 1) {
cin >> x >> y;
x--, y--;
cout << (pre[x] > y ? "YES" : "NO") << endl;
}
return;
}
|
E1
题目大意：这是该题目的简单版本。本版本与其它版本的区别在于本版本中 $t$ 和 $n$ 的数据范围更小。只有在你解决了所有版本的本题后，才能 hack 其他人。Maple 得到了一棵有根树，这棵树有 $n$ 个顶点，编号为 $1$ 到 $n$，根节点编号为 $1$。树上每个顶点都被标记为 $0$ 或 $1$。遗憾的是，Maple 忘记了各个顶点的具体标记，但他只记得正好有 $k$ 个节点被标记为 $0$，其余 $n-k$ 个节点被标记为 $1$。对于每一个顶点，我们将其“名称”定义为一串二进制字符串，该字符串将从根节点到该节点路径上，所有节点的标记顺次拼接而成。
数据范围：$1 \le t \le 50$，$2 \leq n \leq 1000$，$0 \leq k \leq n$，$1 \leq p_i \le i-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
| using i128 = __int128_t;
void solve() {
ll n, k;
cin >> n >> k;
vl pa(n);
vvl ma(n);
rep(i, 1, n - 1) {
cin >> pa[i];
pa[i]--;
ma[pa[i]].push_back(i);
ma[i].push_back(pa[i]);
}
vl cnt(n + 1);
ll mixx = LLONG_MAX;
auto dfs = [&](this auto&& dfs, int x, int pa, int d) -> void {
cnt[d]++;
for (auto& p : ma[x]) {
if (p == pa) continue;
dfs(p, x, d + 1);
}
if (sz(ma[x]) == 1 && x != 0) mixx = min(mixx, 1LL * d);
return;
};
dfs(0, -1, 0);
ll tot = 0;
rep(i, 0, mixx) tot += cnt[i];
vb dp(tot + 1, false);
dp[0] = true;
rep(i, 0, mixx) { frep(j, tot, cnt[i]) dp[j] = dp[j] | dp[j - cnt[i]]; }
rep(i, 0, tot) {
if (!dp[i]) continue;
if (i <= k && tot - i <= n - k) {
cout << mixx + 1 << endl;
return;
}
}
cout << mixx << endl;
return;
}
|
E2
题目大意：Maple 拥有一棵有根树，这棵树有 $n$ 个顶点，编号为 $1$ 到 $n$，其中根节点编号为 $1$。树中的每个顶点都被标记为 $0$ 或 $1$。不幸的是，Maple 忘记了这些顶点的标记，只记得树中恰好有 $k$ 个顶点被标记为 $0$，$n - k$ 个顶点被标记为 $1$。对每个顶点，我们将其“名字”定义为从根节点到该顶点路径上所有顶点标记串联而成的二进制字符串。
数据范围：$1 \leq t \leq 10^4$，$2 \leq n \leq 2 \cdot 10^5$，$0 \leq k \leq n$，$1 \leq p_i \leq i,1$，$\sum n \le 2 \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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| using i128 = __int128_t;
const ll maxx = 2e5 + 5;
void solve() {
ll n, k;
cin >> n >> k;
vl pa(n);
vvl ma(n);
rep(i, 1, n - 1) {
cin >> pa[i];
pa[i]--;
ma[pa[i]].push_back(i);
ma[i].push_back(pa[i]);
}
vl cnt(n + 1);
ll mixx = LLONG_MAX;
auto dfs = [&](this auto&& dfs, int x, int pa, int d) -> void {
cnt[d]++;
for (auto& p : ma[x]) {
if (p == pa) continue;
dfs(p, x, d + 1);
}
if (sz(ma[x]) == 1 && x != 0) mixx = min(mixx, 1LL * d);
return;
};
dfs(0, -1, 0);
ll tot = 0;
rep(i, 0, mixx) tot += cnt[i];
vl cnt2(n + 1);
rep(i, 0, mixx) cnt2[cnt[i]]++;
bitset<maxx + 1> dp;
dp[0] = 1;
rep(i, 1, n) {
if (!cnt2[i]) continue;
for (int j = 1; cnt2[i] > 0; j <<= 1) {
dp |= dp << (min(1LL * j, cnt2[i]) * i);
cnt2[i] -= min(cnt2[i], 1LL * j);
}
}
rep(i, 0, tot) {
if (!dp[i]) continue;
if (i <= k && tot - i <= n - k) {
cout << mixx + 1 << endl;
return;
}
}
cout << mixx << endl;
return;
}
|
