AtCoder Beginner Contest 赛情分析及题解 | 汇总（更新至 ABC 463）
我把自己练习过的AtCoder ABC题目都整理了一下。虽然网站上有许多高手的解法，但因为我自己也是初学者，所以只用了比较容易理解的方法来分析和解答。如果你也在学习的话，希望这些内容能对你有一点帮助。
ABC 464
赛情分析
| 题号 | 题目名称 | 难度 | 考察算法 | 一句话思路总结 |
|---|---|---|---|---|
| A | Decisive Battle | ⭐ | 字符串遍历 / 计数 | 遍历字符串S SS统计字符E和W的出现次数，分别代表东军和西军士兵人数，直接比较两个计数器大小输出East或West，由于字符串长度为奇数保证结果必不相等，时间复杂度O ( ∣ S ∣ ) O(|S|)O(∣S∣)，空间复杂度O ( 1 ) O(1)O(1)。 |
| B | Crop | ⭐⭐ | 模拟 / 二维数组边界裁剪 | 分别从上、下、左、右四个方向扫描二维图像，用标记数组记录需要移除的全白行/列，最后输出未被标记的像素即可；更简洁的做法是直接预处理出包含黑色像素的最小行区间和最小列区间，只输出该区间内的像素，时间复杂度O ( H × W ) O(H \times W)O(H×W)，空间复杂度O ( H × W ) O(H \times W)O(H×W)。 |
| C | Plumage Palette | ⭐⭐⭐ | 双指针 + 哈希表（map） | 将所有鸟按变色天数D i D_iDi升序排序，用map维护当前各颜色的鸟的数量，初始时所有鸟为颜色A i A_iAi；然后用双指针遍历天数i = 1 ∼ M i=1 \sim Mi=1∼M，对于每一天将所有D j = i D_j = iDj=i的鸟从颜色A j A_jAj改为B j B_jBj（对应map中计数减1/加1，计数为0时删除），每天输出map.size()即为当天颜色种类数，时间复杂度O ( N log N + M + N log N ) O(N \log N + M + N \log N)O(NlogN+M+NlogN)（排序 + 遍历 +map操作），空间复杂度O ( N ) O(N)O(N)。 |
| D | Celester | ⭐⭐⭐ | 线性DP（一维状态转移） | 定义d p [ i ] [ 0 / 1 ] dp[i][0/1]dp[i][0/1]表示第i ii天最终为雨天(0)/晴天(1)时的最大幸福值，初始状态根据是否改变第1天天气确定，然后按天递推：d p [ i ] [ j ] = max k ∈ { 0 , 1 } ( d p [ i − 1 ] [ k ] + c o s t ( j ) + g a i n ( k , j ) ) dp[i][j] = \max_{k \in \{0,1\}}(dp[i-1][k] + cost(j) + gain(k,j))dp[i][j]=maxk∈{0,1}(dp[i−1][k]+cost(j)+gain(k,j))，其中c o s t ( j ) cost(j)cost(j)为改变天气的代价（0 00或− X i -X_i−Xi），g a i n ( k , j ) gain(k,j)gain(k,j)为若k = 0 k=0k=0且j = 1 j=1j=1则获得Y i − 1 Y_{i-1}Yi−1收益，最终答案为max ( d p [ n ] [ 0 ] , d p [ n ] [ 1 ] ) \max(dp[n][0], dp[n][1])max(dp[n][0],dp[n][1])，时间复杂度O ( T × N ) O(T \times N)O(T×N)，空间复杂度O ( N ) O(N)O(N)。 |
| E | Fill-Rect Query | ⭐⭐⭐ | 逆向DP / 后缀最大值传播 | 由于每次操作都是覆盖以( 1 , 1 ) (1,1)(1,1)为左上角的矩形，格子( i , j ) (i,j)(i,j)的最终颜色由所有满足R k ≥ i R_k \ge iRk≥i且C k ≥ j C_k \ge jCk≥j的操作中编号最大的那个决定；将每次操作仅记录在其右下角( R k , C k ) (R_k, C_k)(Rk,Ck)，然后从右下角向左上角做二维DP：a [ i ] [ j ] = max ( a [ i ] [ j ] , a [ i + 1 ] [ j ] , a [ i ] [ j + 1 ] ) a[i][j] = \max(a[i][j], a[i+1][j], a[i][j+1])a[i][j]=max(a[i][j],a[i+1][j],a[i][j+1])，a [ i ] [ j ] a[i][j]a[i][j]即为覆盖( i , j ) (i,j)(i,j)的最后操作编号，输出对应字符即可，时间复杂度O ( H × W + Q ) O(H \times W + Q)O(H×W+Q)，空间复杂度O ( H × W ) O(H \times W)O(H×W)。 |
| F |
题目
题解：洛谷 AT_abc464_a Decisive Battle
题解：洛谷 AT_abc464_b Crop
题解：洛谷 AT_abc464_c Plumage Palette
题解：洛谷 AT_abc464_d Celester
题解：洛谷 AT_abc464_e Fill-Rect Query
ABC 463
赛情分析
| 题号 | 题目名称 | 难度 | 考察算法 | 一句话思路总结 |
|---|---|---|---|---|
| A | 16:9 | ⭐ | 模拟 / GCD | 用最大公约数将宽高比化简，判断是否等于16 : 9 16:916:9。 |
| B | Train Reservation | ⭐ | 模拟 | 遍历所有列车，检查目标列X XX是否存在至少一个o。 |
| C | Tallest at the Moment | ⭐⭐ | 排序 + 二分 + 后缀最大值 | 按离开时间排序后预处理后缀最大身高，对每个查询二分找到第一个未离开的位置，取后缀最大值。 |
| D | Maximize the Gap | ⭐⭐⭐ | 整数二分 + 贪心判定 | 按右端点排序后二分答案，贪心验证是否能选出K KK块两两不重叠且间距至少为m i d midmid的布。 |
| E | Roads and Gates | ⭐⭐⭐⭐ | Dijkstra + 虚拟节点 | 传送门两两之间的完全图通过虚拟节点拆分为O ( N ) O(N)O(N)条边，再跑 Dijkstra 求最短路。 |
| F | Senshuraku | ⭐⭐⭐⭐⭐ | 组合概率 + 分类讨论 | 枚举N NN场比赛结果，利用组合数计算"最大值选手中均匀随机选冠军"的概率，对998244353 998244353998244353取模。 |
题目
题解：洛谷 AT_abc463_a 16:9
题解：洛谷 AT_abc463_b Train Reservation
题解：洛谷 AT_abc463_c Tallest at the Moment
题解：洛谷 AT_abc463_d Maximize the Gap
题解：洛谷 AT_abc463_e Roads and Gates
题解：洛谷 AT_abc463_f Senshuraku