AtCoder Weekday Consest 赛情分析及题解 | 汇总（更新至 AWC 0101 Beta）

2026/7/5 15:02:57

我把自己练习过的AtCoder AWC题目都整理了一下。虽然网站上有许多高手的解法，但因为我自己也是初学者，所以只用了比较容易理解的方法来分析和解答。如果你也在学习的话，希望这些内容能对你有一点帮助。

AWC 0101 Beta

赛情分析

题号	题目名称	难度	考察算法	一句话思路总结
A	City with Power Shortage	⭐	模拟 / 简单统计	遍历所有输电线路，将每条线路的容量W j W_jWj分别累加到其两端城市U j U_jUj和V j V_jVj的可供电量T i T_iTi中，最后遍历所有城市统计满足T i < S i T_i < S_iTi<Si的"电力不足城市"数量，时间复杂度O ( N + M ) O(N + M)O(N+M)，空间复杂度O ( N ) O(N)O(N)。
B	A Single Strike of Dominoes	⭐⭐⭐	整数二分 + 模拟验证	对施加的力X XX进行二分搜索（范围[ 1 , 10 9 ] [1, 10^9][1,109]），每次用`check(x)`模拟：先将所有柱子耐久度减去X XX，然后从左到右遍历，若第i ii根柱子倒塌（耐久度≤ 0 \le 0≤0）则第i + 1 i+1i+1根额外减1 11，最后判断是否全部倒塌，根据`check`结果调整二分边界，时间复杂度O ( N log ⁡ A max ⁡ ) O(N \log A_{\max})O(NlogAmax)，空间复杂度O ( N ) O(N)O(N)。
C	Chain of Infection	⭐⭐⭐⭐	树形DP / BFS层级传播（多轮感染模拟）	初始感染D i > 0 D_i > 0Di>0的节点，然后按轮次从叶子向上模拟感染传播：每轮中所有满足"被感染子节点数 $a > $ 未被感染子节点数b bb"的未感染节点同时被感染，重复直到无新增感染，由于每轮感染状态基于该轮开始时的状态同时判定，可用BFS按层处理或反复DFS直到收敛，时间复杂度O ( N × 轮数 ) O(N \times \text{轮数})O(N×轮数)。
D	Tiling Plan	⭐⭐⭐	GCD + 因子枚举	先求所有房间( H i , W i ) (H_i, W_i)(Hi,Wi)各自最大公约数的总GCDg = gcd ⁡ ( g 1 , g 2 , … , g N ) g = \gcd(g_1, g_2, \ldots, g_N)g=gcd(g1,g2,…,gN)（其中g i = gcd ⁡ ( H i , W i ) g_i = \gcd(H_i, W_i)gi=gcd(Hi,Wi)），则合法边长d dd必为g gg的因子；枚举g gg的所有因子并按从大到小排序，对每个候选d dd验证是否满足H i d × W i d ≡ 0 ( m o d S i ) \frac{H_i}{d} \times \frac{W_i}{d} \equiv 0 \pmod{S_i}dHi×dWi≡0(modSi)（即瓷砖数量为S i S_iSi的倍数），第一个满足条件的即为最大边长，时间复杂度O ( g × N ) O(\sqrt{g} \times N)O(g×N)，空间复杂度O ( g ) O(\sqrt{g})O(g)。
E	Choosing Flowerbed Intervals	⭐⭐⭐⭐	双指针 + 单调队列 + 哈希表	用双指针维护满足两个条件的最大窗口：右指针j jj从左到右枚举，用单调递增/递减队列分别维护区间[ i , j ] [i,j][i,j]的最小值和最大值（保证条件2），用`map`维护区间内不同品种的数量D DD（保证条件1），当D × ( j − i + 1 ) > K D \times (j-i+1) > KD×(j−i+1)>K或max ⁡ − min ⁡ > M \max - \min > Mmax−min>M时收缩左指针i ii直到满足条件，以j jj为右端点的合法区间数为( j − i + 1 ) (j-i+1)(j−i+1)，累加得到答案，时间复杂度O ( N log ⁡ N ) O(N \log N)O(NlogN)（`map`操作），空间复杂度O ( N ) O(N)O(N)。

题目

题解：AtCoder AT_awc0101_a City with Power Shortage

题解：AtCoder AT_awc0101_b A Single Strike of Dominoes

题解：AtCoder AT_awc0101_c Chain of Infection

题解：AtCoder AT_awc0101_d Tiling Plan

题解：AtCoder AT_awc0101_e Choosing Flowerbed Intervals

AWC 0098 Beta

赛情分析

题号	题目名称	难度	考察算法	一句话思路总结
A	Error Analysis of Temperature Forecasts	⭐	模拟	对每个地点计算D DD天预报误差绝对值之和，取最大值。
B	Library Book Lending	⭐⭐	整数二分 / 排序	将书籍要求T j T_jTj排序，对每个学生S i S_iSi二分查找满足T j ≤ S i T_j \le S_iTj≤Si的数量。
C	Highway Discount Pass	⭐⭐⭐	KMP + 贪心	KMP找出所有T TT在S SS中的匹配位置，贪心选不重叠区间最大化数量。
D	City Tour Rally	⭐⭐⭐	线性DP-二维	d p [ i ] [ j ] dp[i][j]dp[i][j]表示第i ii天在城市j jj的最大分数，反向建图枚举前驱转移。
E	Maintenance of Waterways	⭐⭐⭐⭐⭐	树形DP	d p 0 [ u ] dp0[u]dp0[u]/d p 1 [ u ] dp1[u]dp1[u]表示父边不由/由u uu负责的最小额外费用，贪心排序子边费用差枚举选择数量。

题目

题解：AtCoder AT_awc0098_a Error Analysis of Temperature Forecasts

题解：AtCoder AT_awc0098_b Library Book Lending

题解：AtCoder AT_awc0098_c Highway Discount Pass

题解：AtCoder AT_awc0098_d City Tour Rally

题解：AtCoder AT_awc0098_e Maintenance of Waterways

AWC 0089 Beta

赛情分析

题号	题目名称	难度	考察算法	一句话思路总结
A	Correcting the Household Account Book	⭐	模拟 / 前缀和	维护总和，每次操作直接减去被清零位置的值即可。
B	Connecting Pipes	⭐⭐	贪心 / 排序	将管道按有效长度降序排序，依次选取并维护最大长度，注意每多选一根管道需扣除连接成本K。
C	A Walk to Cherry Blossom Viewing	⭐⭐⭐	双指针（滑动窗口）	用滑动窗口维护成本不超过预算B的连续散步道区间，动态调整左右指针并更新最大景点分数和。
D	Cheapest Route	⭐⭐⭐	Dijkstra最短路	边权为两端城市人口乘积，从城市1跑单源最短路，取所有机场城市的最小距离。
E	Painting the Fence	⭐⭐⭐⭐⭐	离散化 + 扫描线 + 差分	将区间端点离散化后用扫描线维护当前覆盖集合，利用差分数组统计忽略K个连续指令后的最大覆盖长度。

题目

题解：AtCoder AT_awc0089_a Correcting the Household Account Book

题解：AtCoder AT_awc0089_b Connecting Pipes

题解：AtCoder AT_awc0089_c A Walk to Cherry Blossom Viewing

题解：AtCoder AT_awc0089_d Cheapest Route

题解：AtCoder AT_awc0089_e Painting the Fence

AWC 0088 Beta

赛情分析

题号	题目名称	难度	考察算法	一句话思路总结
A	Bus Departure Time	⭐	模拟	所有学生上车完毕的时间为T i T_iTi的最大值，加上K KK即为发车信号时间。
B	Bus Tour Group Division	⭐⭐	贪心 / 排序	将出发时间排序后贪心分组，每组以第一个元素为基准，差值超过K KK时开启新组。
C	Farm Harvest Festival	⭐⭐⭐	差分 / 前缀和	用差分数组标记所有被覆盖过的田地，前缀和还原后累加被覆盖位置的A i A_iAi。
D	Control Panel Operation Sequence	⭐⭐⭐⭐	全排列枚举 + 哈希表	N ≤ 9 N \leq 9N≤9允许枚举N ! N!N!种操作顺序，用`map`离线记录每种结果序列的出现次数。
E	Intervals That Can Be Arranged Alternately	⭐⭐⭐⭐⭐	莫队算法	好区间判定转化为前缀差分数组中两位置差值绝对值不超过 1，用莫队离线统计数对。