我把自己练习过的AtCoder ABC题目都整理了一下。虽然网站上有许多高手的解法但因为我自己也是初学者所以只用了比较容易理解的方法来分析和解答。如果你也在学习的话希望这些内容能对你有一点帮助。ABC 464赛情分析题号题目名称难度考察算法一句话思路总结ADecisive Battle⭐字符串遍历 / 计数遍历字符串S SS统计字符E和W的出现次数分别代表东军和西军士兵人数直接比较两个计数器大小输出East或West由于字符串长度为奇数保证结果必不相等时间复杂度O ( ∣ S ∣ ) O(|S|)O(∣S∣)空间复杂度O ( 1 ) O(1)O(1)。BCrop⭐⭐模拟 / 二维数组边界裁剪分别从上、下、左、右四个方向扫描二维图像用标记数组记录需要移除的全白行/列最后输出未被标记的像素即可更简洁的做法是直接预处理出包含黑色像素的最小行区间和最小列区间只输出该区间内的像素时间复杂度O ( H × W ) O(H \times W)O(H×W)空间复杂度O ( H × W ) O(H \times W)O(H×W)。CPlumage Palette⭐⭐⭐双指针 哈希表map将所有鸟按变色天数D i D_iDi​升序排序用map维护当前各颜色的鸟的数量初始时所有鸟为颜色A i A_iAi​然后用双指针遍历天数i 1 ∼ M i1 \sim Mi1∼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(NlogNMNlogN)排序 遍历 map操作空间复杂度O ( N ) O(N)O(N)。DCelester⭐⭐⭐线性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 k0k0且j 1 j1j1则获得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)。EFill-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​)然后从右下角向左上角做二维DPa [ i ] [ j ] max ⁡ ( a [ i ] [ j ] , a [ i 1 ] [ j ] , a [ i ] [ j 1 ] ) a[i][j] \max(a[i][j], a[i1][j], a[i][j1])a[i][j]max(a[i][j],a[i1][j],a[i][j1])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×WQ)空间复杂度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 QueryABC 463赛情分析题号题目名称难度考察算法一句话思路总结A16:9⭐模拟 / GCD用最大公约数将宽高比化简判断是否等于16 : 9 16:916:9。BTrain Reservation⭐模拟遍历所有列车检查目标列X XX是否存在至少一个o。CTallest at the Moment⭐⭐排序 二分 后缀最大值按离开时间排序后预处理后缀最大身高对每个查询二分找到第一个未离开的位置取后缀最大值。DMaximize the Gap⭐⭐⭐整数二分 贪心判定按右端点排序后二分答案贪心验证是否能选出K KK块两两不重叠且间距至少为m i d midmid的布。ERoads and Gates⭐⭐⭐⭐Dijkstra 虚拟节点传送门两两之间的完全图通过虚拟节点拆分为O ( N ) O(N)O(N)条边再跑 Dijkstra 求最短路。FSenshuraku⭐⭐⭐⭐⭐组合概率 分类讨论枚举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