ABC464-①C-差分②D-DP③倒序处理+并查集#

Tasks - Japanese Student Championship 2026 -Advance- Qualification (AtCoder Beginner Contest 464)

https://www.wolai.com/afk85a38xnsRy9x5g5b8EM

B-枚举#

问题#

有一幅高度为 $H$ 像素、宽度为 $W$ 像素的黑白图像。从上往下 $i$ 行、从左往上 $j$ 列的像素的颜色是一个字符 $C_{i,j}$ ，其中.代表白色，#代表黑色。

从图像的顶部、底部、左侧和右侧边缘，删除所有像素都是白色的行和列。具体来说，依次执行以下操作：

当图像最顶端一行全部为白色时，重复删除最顶端一行。
当图像最下面一行全白时，重复删除最下面一行。
当图像最左侧一列全白时，重复删除最左侧一列。
当图像最右边一列全白时，重复删除最右边一列。

输出处理后的图像。

给定的图像至少包含一个黑色像素。

题解#

找到四个裁剪边界：

上边界 top：第一个包含 # 的行索引
下边界 bottom：最后一个包含 # 的行索引
左边界 left：第一个包含 # 的列索引
右边界 right：最后一个包含 # 的列索引

然后输出 [top, bottom] 行、[left, right] 列的子矩阵即可。

1
h, w = map(int, input().split())
2
grid = [input().strip() for _ in range(h)]
3
top = 0
4
while top < h:
5
    if '#' in grid[top]:
6
        break
7
    top += 1
8
bottom = h - 1
9
while bottom >= top:
10
    if '#' in grid[bottom]:
11
        break
12
    bottom -= 1
13
left = 0
14
while left < w:
15
    ok = any(grid[i][left] == '#' for i in range(top, bottom + 1))
16
    if ok:
17
        break
18
    left += 1
19
right = w - 1
20
while right >= left:
21
    ok = any(grid[i][right] == '#' for i in range(top, bottom + 1))
22
    if ok:
23
        break
24
    right -= 1
25
for i in range(top, bottom + 1):
26
    print(grid[i][left:right + 1])

C-差分#

题意#

高桥在 $M$ 天里观察了 $N$ 只鸟，编号为 $1, 2, \dots, N$ 。高桥观察到的每只鸟都有 $N$ 种颜色，编号为 $1, 2, \dots, N$ ，这些鸟有一个有趣的特点：它们的颜色在观察期间会发生变化。

在 $D_i - 1$ 天或之前观察到的鸟 $i$ 的颜色为 $A_i$ ，而在 $D_i$ 天或之后观察到的鸟的颜色为 $B_i$ 。这里，如果是 $D_i = 1$ ，则该鸟的颜色与 $1$ 日的观察结果相比是 $B_i$ ，如果是 $A_i = B_i$ ，则该鸟的颜色在观察期间没有变化。

对于每个 $j = 1, 2, \dots, M$ ，求出 $j$ 这一天鸟的不同颜色的数量。

题解#

把每只鸟的”颜色存在性”拆成事件：

第 1 天：颜色 Ai 出现
第 Di 天：颜色 Ai 消失，颜色 Bi 出现

维护：

cnt[color]：当前该颜色的鸟数
ans：当前不同颜色数（cnt[color] > 0 的个数）

cnt[color] == 0 且 delt == 1：新颜色出现

cnt[color] == 1 且 delt == -1：颜色消失

1
n,m = map(int,input().split())
2
eve = [[] for _ in range(n + 2)]
3
for _ in range(n):
4
    a,d,b = map(int,input().split())
5
    if d > 1:
6
        eve[1].append((a,1))
7
        eve[d].append((a,-1))
8
    eve[d].append((b,1))
9
cnt = [0]*(n + 1)
10
ans = 0
11
for day in range(1,m+1):
12
    for col,delt in eve[day]:
13
        if cnt[col] == 0 and delt == 1:
14
            ans += 1
15
        elif cnt[col] == 1 and delt == -1:
16
            ans -= 1
17
        cnt[col] += delt
18
    print(ans)

D-DP#

问题#

未来 $N$ 天的天气以字符串 $S$ 的形式给出。如果 $S$ 的 $i$ -th 字符是 “S”，那么 $i$ 天的天气是晴天；如果是 “R”，那么 $i$ 天的天气是雨天。另外，您当前的幸福指数为 $0$ 。

你可以执行以下操作任意次数，可能为零：

用 $1 \le i \le N$ 选择一个整数 $i$ 。
如果 $i$ 这一天的天气是晴天，则将其改为雨天；如果是雨天，则将其改为晴天。
然而，如果你改变 $i$ 这一天的天气，你的幸福感会减少 $X_i$ 。

执行操作后，您的幸福值会根据最终天气按照以下条件增加：

对于每个带有 $1 \le i \le N-1$ 的整数 $i$ ，如果修改后 $i$ 这一天的天气是阴雨天，而 $i+1$ 这一天的天气是晴天，则您的幸福感会增加 $Y_i$ 。

请找出通过操作可以获得的最大幸福值。

题解#

收益只取决于相邻两天的最终状态（R 后跟 S）。

我们只需要知道每一天最终是 S 还是 R：

初始状态由 S 给出
翻转一次需要花费 Xi
翻转两次等于没翻（恢复原状），所以每天要么翻要么不翻

定义 dp[i][state]：考虑前 i 天，第 i 天状态为 state（0=S, 1=R）时的最大幸福值。

对于第 i 天：

初始状态：init = 0 if S[i]=='S' else 1
翻转花费：如果最终状态 ≠ 初始状态，花费 XiXi

从前一天状态 prev 转移到当天状态 curr：

dp[i][curr] = max(dp[i][curr], dp[i-1][prev] - cost + bonus)

其中：

cost = X_i 如果需要翻转，否则 0
bonus = Y_{i-1} 如果 prev=R 且 curr=S，否则 0

初始化：

dp[0][S[0]=='S' ? 0 : 1] = 0（不翻转第一天的初始状态）

dp[0][S[0]=='S' ? 1 : 0] = -X_1（翻转第一天）

1
for _ in range(int(input())):
2
    n = int(input())
3
    s = input().strip()
4
    x = list(map(int, input().split()))
5
    y = list(map(int, input().split()))
6
    inf = -10**18
7
    dp = [[inf,inf] for _ in range(n)]
8
    one = 0 if s[0] == 'S' else 1
9
    dp[0][one] = 0
10
    dp[0][1-one] = -x[0]
11
    for i in range(1,n):
12
        one = 0 if s[i] == 'S' else 1
13
        for cur in [0,1]:
14
            c = 0 if cur == one else x[i]
15
            for pre in [0,1]:
16
                if pre == 1 and cur == 0:
17
                    cc = y[i-1]
18
                else:
19
                    cc = 0
20
                val = dp[i-1][pre] - c + cc
21
                if val > dp[i][cur]:
22
                    dp[i][cur] = val
23
    print(max(dp[n-1][0],dp[n-1][1]))

E-倒序处理+并查集#

问题#

有一个 $H \times W$ 网格。一开始，每个单元格上都写着 “A”。从上往下第 $i$ 行，从左往上第 $j$ 列的单元格用 $(i, j)$ 表示。

我们将依次进行 $Q$ 次运算。在 $i$ -th 操作中，用大写英文字母 $X_i$ 覆盖矩形中左上角单元格 $(1, 1)$ 和右下角单元格 $(R_i, C_i)$ 的所有单元格。

完成所有操作后，输出网格。

题解#

1. 所有操作的左上角都是 (1,1)

这意味着每次操作覆盖的范围总是从第 1 行第 1 列开始。矩形形状固定为”前缀矩形”。

2. 后面操作覆盖前面操作

如果正序处理，后面的操作会覆盖前面的。因此倒序处理可以直接确定每个格子的最终值：第一次被赋值就是最终值。

3. 每个格子只需赋值一次

倒序处理时，一旦某个格子被赋值，就不需要再改变。我们需要高效地跳过已经处理过的格子。

n_col[i]：第 i 行下一个未填充的列索引（0-indexed）
nxt_row：行并查集，nxt_row[i] 指向第 i 行之后第一个未填满的行
find(x)：并查集的查找函数，带路径压缩

倒序遍历所有操作 (R, C, X)：

找到第一个未填满的行 i = find(0)
对于所有 i < R 的行：
- 在该行中，从 n_col[i] 开始填充到 C-1 列，全部赋值为 X
- 更新 n_col[i]
- 如果该行填满了（n_col[i] >= W），用并查集标记该行为已满：nxt_row[i] = find(i + 1)
- 跳到下一个未填满的行：i = find(i + 1)

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main() {
4
    ios::sync_with_stdio(false);
5
    cin.tie(nullptr);
6
    int h, w, q;
7
    cin >> h >> w >> q;
8
    vector<int> r(q), c(q);
9
    vector<char> x(q);
10
    for (int i = 0; i < q; ++i) {
11
        cin >> r[i] >> c[i] >> x[i];
12
    }
13
    vector<string> grid(h, string(w, 'A'));
14
    vector<int> n_col(h, 0);
15
    vector<int> nxt_row(h + 1);
16
    iota(nxt_row.begin(), nxt_row.end(), 0);
17
    function<int(int)> find = [&](int v) -> int {
18
        while (nxt_row[v] != v) {
19
            nxt_row[v] = nxt_row[nxt_row[v]];
20
            v = nxt_row[v];
21
        }
22
        return v;
23
    };
24
    for (int idx = q - 1; idx >= 0; --idx) {
25
        int cur_r = r[idx];
26
        int cur_c = c[idx];
27
        char cur_x = x[idx];
28
        int i = find(0);
29
        while (i < cur_r) {
30
            int &col = n_col[i];
31
            while (col < cur_c && col < w) {
32
                grid[i][col] = cur_x;
33
                ++col;
34
            }
35
            if (col >= w) {
36
                nxt_row[i] = find(i + 1);
37
            }
38
            i = find(i + 1);
39
        }
40
    }
41
    for (int i = 0; i < h; ++i) {
42
        cout << grid[i] << '\n';
43
    }
44
    return 0;
45
}

音乐

音乐

ABC464-①C-差分②D-DP③倒序处理+并查集#

B-枚举#

问题#

题解#

C-差分#

题意#

题解#

D-DP#

问题#

题解#

E-倒序处理+并查集#

问题#

题解#

音乐

目录