B
题目大意：Alice 正在为她的派对准备一个蛋糕。但由于时间紧迫，蛋糕上的糖霜铺得不均匀。为了解决这个问题，Alice 决定将刀子放在某个整数高度，然后从左到右扫平糖霜，使糖霜铺得平整。具体地，设第 $i$ 个位置的糖霜高度为 $a_i$。假设 Alice 将刀子放在某个整数高度 $h$。如果第 $i$ 个位置的糖霜高度大于 $h$，那么多余的糖霜会被推到第 $i+1$ 个位置。最后一个位置 $n$ 上多余的糖霜会被完全推出蛋糕之外。Alice 和她的朋友们非常喜欢蛋糕上的糖霜。
数据范围：$1 \le t \le 10^4$，$2 \leq n \leq 2\cdot 10^5$，$1 \leq a_i \leq 10^9$，$\sum n \le 2\cdot 10^5$。
思路：
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];
vl pre(n);
pre[0] = a[0];
rep(i, 1, n - 1) pre[i] = pre[i - 1] + a[i];
vl res(n);
res[0] = a[0];
rep(i, 1, n - 1) res[i] = min(res[i - 1], pre[i] / (i + 1));
rep(i, 0, n - 1) cout << res[i] << ' ';
cout << endl;
return;
}
|
C1
题目大意：这是该问题的 Easy 版本。两个版本的区别在于本版本中 $n$、$x$、$s$、$t$ 的约束更小。只有在你完成了所有版本后才能进行 hack。Alice 的朋友们来到了派对，现在他们排成一队准备进入派对。派对上有 $x$ 张桌子，每张桌子有 $s$ 个座位。每个座位只能坐一个人。每位朋友有以下三种性格之一： - 内向型（I）：必须坐在一个空桌子上； - 外向型（E）：必须坐在一个非空桌子上； - 中间型（A）：可以坐在任何桌子上。一开始，每个座位都是空的。然而，因为 Alice 正在吃蛋糕，她的朋友们已经排好队了，这个顺序 Alice 无法改变。对于队列中的每个人，Alice 必须给他们分配一个桌子，或者让他们离开派对。
数据范围：$1 \leq t \leq 500$，$1 \leq n, x, s \leq 3000$，$\sum n \le 3000$。
思路：
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
| void solve() {
ll n, x, s;
cin >> n >> x >> s;
string t;
cin >> t;
ll cnt = 0;
ll tem = 0;
ll cur = 0;
ll ans = 0;
rep(i, 0, n - 1) {
if (t[i] == 'I') {
if (cnt == x) continue;
cnt++;
tem += s - 1;
ans++;
} else if (t[i] == 'A') {
if (tem > 0) {
tem--;
cur++;
ans++;
} else if (cnt < x) {
cnt++;
tem += s - 1;
ans++;
}
} else {
if (tem > 0) {
tem--;
ans++;
} else if (cnt < x && cur > 0) {
cur--;
cnt++;
tem += s - 1;
ans++;
}
}
}
cout << ans << endl;
return;
}
|
C2
题目大意：这是该题目的 Hard 版本。与其它版本的区别在于本版本中 $n$、$x$、$s$、$t$ 的约束范围更大。只有解决了所有版本后才可以进行 Hack。Alice 的朋友们来到派对，现在他们正排队准备进入派对。派对上有 $x$ 张桌子，每张桌子有 $s$ 个座位。每个座位只能坐一个人。每位朋友有以下三种性格之一： - 内向型（I）：必须坐在一张空桌子上。- 外向型（E）：必须坐在一张非空桌子上。- 两性型（A）：可以坐在任何桌子上。最开始，所有座位都是空的。然而，由于 Alice 在吃蛋糕，她的朋友们已经排好队了，Alice 不能更改他们的顺序。对于队伍中的每个人，Alice 必须为他分配桌子或将其请出派对。每个人都在下一个人被分配桌子之前就已经就座。
数据范围：$1 \le t \le 10^4$，$1 \le n,x,s \le 2 \cdot 10^5$，$\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
| void solve() {
ll n, x, s;
cin >> n >> x >> s;
string t;
cin >> t;
ll cnt = 0;
ll tem = 0;
ll cur = 0;
ll ans = 0;
rep(i, 0, n - 1) {
if (t[i] == 'I') {
if (cnt == x) continue;
cnt++;
tem += s - 1;
ans++;
} else if (t[i] == 'A') {
if (tem > 0) {
tem--;
cur++;
ans++;
} else if (cnt < x) {
cnt++;
tem += s - 1;
ans++;
}
} else {
if (tem > 0) {
tem--;
ans++;
} else if (cnt < x && cur > 0) {
cur--;
cnt++;
tem += s - 1;
ans++;
}
}
}
cout << ans << endl;
return;
}
|
D
题目大意：Alice 完成了一个有 $n$ 层的魔法分层蛋糕，每一层都比下面的所有层都小（即第 $1$ 层最小，第 $n$ 层最大）。现在她需要你的帮助，将蛋糕从厨房运送到派对现场。由于无法一次搬运整个蛋糕，她还为你准备了一个仓库，以辅助运输过程。由于蛋糕具有魔力，第 $i$ 层蛋糕可移动，当且仅当它上方恰好有 $a_i$ 层蛋糕。每一步操作中，你可以选择任意一个位置上的正好可移动的蛋糕层，将其移动到另一个位置上分层蛋糕的顶部。然而，为了维持蛋糕的结构，如果目标位置已有分层蛋糕，被移动的蛋糕层必须放在一个比它严格更大的蛋糕层上。由于派对即将开始，我们必须尽快行动。需要帮助 Alice 在 $2^n$ 步内将蛋糕全部运输至派对现场，否则请报告不可能。
数据范围：$1 \le t \le 10000$，$1 \le n \le 20$，$0 \leq a_i \leq n$，$\sum 2^n \le 2^{20}$。
思路：
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
| void solve() {
ll n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, n - 1) {
if (a[i] > i) {
cout << "NO" << endl;
return;
}
}
vector<trl> res;
vl tem(n);
auto dfs = [&](this auto&& dfs, ll t, ll x, ll y, ll d) -> void {
if (t == 0) return;
ll tem2 = (d == t ? x : y);
if (tem[t - 1] != tem2) {
dfs(t - 1, tem[t - 1], 3 - tem[t - 1] - tem2, a[t - 1]);
res.emplace_back(t, tem[t - 1] + 1, tem2 + 1);
tem[t - 1] = tem2;
}
dfs(t - 1, x, y, min(d, t - 1));
};
dfs(n, 2, 1, n);
cout << "YES" << endl;
cout << sz(res) << endl;
for (auto& [x, y, z] : res) cout << x << ' ' << y << ' ' << z << endl;
return;
}
|
E
题目大意：现在到了重头戏的时刻：一个很大的 $n \times n$ 的蛋糕。Alice 和她的朋友们想用奶油在蛋糕上装饰成“蛇”的形状。定义大小为 $k$ 的蛇为一条从蛋糕的某个格子出发的长度为 $k$ 的路径，每一步只能向右或向下。经过对蛋糕的深入研究，Alice 认为给这个蛋糕装饰的最佳方式是放置 $n$ 条蛇，其中第 $i$ 条蛇的长度为 $2 \cdot i - 1$。她已经提前准备好了所有的奶油蛇；但有些朋友太兴奋，已经在 Alice 还没规划好如何装饰蛋糕之前随意放置了一些蛇。幸运的是，Alice 发现仍然可以完成装饰。需要帮助她计算可以在不移动任何她朋友已经放好的蛇的情况下装饰蛋糕的方案数。
数据范围：$1 \le t \le 1000$，$1 \le n \le 5000, 0 \le k \le n$，$1 \le s \le 2\cdot n,1$，$1 \le r, c \le n$，$\displaystyle \sum n \le 5000$，$\displaystyle \sum |s| \le 4 \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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| constexpr ll MOD = 1e9 + 7;
ll mul(ll x, ll y) { return x * y % MOD; }
ll qpow(ll x, ll y) {
ll z = 1;
while (y > 0) {
if (y & 1) z = mul(z, x);
x = mul(x, x);
y >>= 1;
}
return z;
} // 求x**y%MOD
// 注意：当MOD为质数时， (x/y)%MOD=(x*(y**(MOD-2)))%MOD，即y在模MOD意义下的逆元为b^{-1} \equiv b^{p-2} mod p
void solve() {
ll n, k;
cin >> n >> k;
vl l(k);
vector<string> ma(k);
vector<pll> ma2(k);
rep(i, 0, k - 1) {
cin >> l[i];
l[i]--;
cin >> ma2[i].first >> ma2[i].second;
ma2[i].first--, ma2[i].second--;
if (!l[i]) continue;
cin >> ma[i];
}
vl cnt(n);
vvl tem(n);
rep(i, 0, k - 1) {
cnt[l[i] / 2] = 1;
tem[l[i] / 2].resize(l[i] / 2 + 1);
ll x = ma2[i].first, y = ma2[i].second;
rep(j, 0, l[i]) {
ll tem2 = x + y;
ll tem3 = abs(tem2 - (n - 1));
ll tem4 = x - max(0LL, tem2 - (n - 1));
tem[l[i] / 2][tem3] = tem4;
if (j == l[i]) break;
if (ma[i][j] == 'D')
x++;
else
y++;
}
}
ll ans = 1;
frep(i, n - 1, 0) {
ll l = 0, r = n - i - 1;
if (cnt[i]) l = r = tem[i][i];
rep(j, i + 1, n - 1) {
if (!cnt[j]) continue;
if (tem[j][i + 1] + 1 == tem[j][i])
r = min(r, tem[j][i + 1]);
else if (tem[j][i + 1] == tem[j][i])
l = max(l, tem[j][i + 1] + 1);
}
ans = mul(ans, (r - l + 1));
}
cout << ans << endl;
return;
}
|
