我把自己练习过的AtCoder AWC题目都整理了一下。虽然网站上有许多高手的解法但因为我自己也是初学者所以只用了比较容易理解的方法来分析和解答。如果你也在学习的话希望这些内容能对你有一点帮助。AWC 0101 Beta赛情分析题号题目名称难度考察算法一句话思路总结ACity 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(NM)空间复杂度O ( N ) O(N)O(N)。BA 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 i1i1根额外减1 11最后判断是否全部倒塌根据check结果调整二分边界时间复杂度O ( N log ⁡ A max ⁡ ) O(N \log A_{\max})O(NlogAmax​)空间复杂度O ( N ) O(N)O(N)。CChain of Infection⭐⭐⭐⭐树形DP / BFS层级传播多轮感染模拟初始感染D i 0 D_i 0Di​0的节点然后按轮次从叶子向上模拟感染传播每轮中所有满足被感染子节点数 $a $ 未被感染子节点数b bb的未感染节点同时被感染重复直到无新增感染由于每轮感染状态基于该轮开始时的状态同时判定可用BFS按层处理或反复DFS直到收敛时间复杂度O ( N × 轮数 ) O(N \times \text{轮数})O(N×轮数)。DTiling 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)ggcd(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​)。EChoosing Flowerbed Intervals⭐⭐⭐⭐双指针 单调队列 哈希表用双指针维护满足两个条件的最大窗口右指针j jj从左到右枚举用单调递增/递减队列分别维护区间[ i , j ] [i,j][i,j]的最小值和最大值保证条件2用map维护区间内不同品种的数量D DD保证条件1当D × ( j − i 1 ) K D \times (j-i1) KD×(j−i1)K或max ⁡ − min ⁡ M \max - \min Mmax−minM时收缩左指针i ii直到满足条件以j jj为右端点的合法区间数为( j − i 1 ) (j-i1)(j−i1)累加得到答案时间复杂度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 IntervalsAWC 0098 Beta赛情分析题号题目名称难度考察算法一句话思路总结AError Analysis of Temperature Forecasts⭐模拟对每个地点计算D DD天预报误差绝对值之和取最大值。BLibrary Book Lending⭐⭐整数二分 / 排序将书籍要求T j T_jTj​排序对每个学生S i S_iSi​二分查找满足T j ≤ S i T_j \le S_iTj​≤Si​的数量。CHighway Discount Pass⭐⭐⭐KMP 贪心KMP找出所有T TT在S SS中的匹配位置贪心选不重叠区间最大化数量。DCity Tour Rally⭐⭐⭐线性DP-二维d p [ i ] [ j ] dp[i][j]dp[i][j]表示第i ii天在城市j jj的最大分数反向建图枚举前驱转移。EMaintenance of Waterways⭐⭐⭐⭐⭐树形DPd 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 WaterwaysAWC 0089 Beta赛情分析题号题目名称难度考察算法一句话思路总结ACorrecting the Household Account Book⭐模拟 / 前缀和维护总和每次操作直接减去被清零位置的值即可。BConnecting Pipes⭐⭐贪心 / 排序将管道按有效长度降序排序依次选取并维护最大长度注意每多选一根管道需扣除连接成本K。CA Walk to Cherry Blossom Viewing⭐⭐⭐双指针滑动窗口用滑动窗口维护成本不超过预算B的连续散步道区间动态调整左右指针并更新最大景点分数和。DCheapest Route⭐⭐⭐Dijkstra最短路边权为两端城市人口乘积从城市1跑单源最短路取所有机场城市的最小距离。EPainting 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 FenceAWC 0088 Beta赛情分析题号题目名称难度考察算法一句话思路总结ABus Departure Time⭐模拟所有学生上车完毕的时间为T i T_iTi​的最大值加上K KK即为发车信号时间。BBus Tour Group Division⭐⭐贪心 / 排序将出发时间排序后贪心分组每组以第一个元素为基准差值超过K KK时开启新组。CFarm Harvest Festival⭐⭐⭐差分 / 前缀和用差分数组标记所有被覆盖过的田地前缀和还原后累加被覆盖位置的A i A_iAi​。DControl Panel Operation Sequence⭐⭐⭐⭐全排列枚举 哈希表N ≤ 9 N \leq 9N≤9允许枚举N ! N!N!种操作顺序用map离线记录每种结果序列的出现次数。EIntervals That Can Be Arranged Alternately⭐⭐⭐⭐⭐莫队算法好区间判定转化为前缀差分数组中两位置差值绝对值不超过 1用莫队离线统计数对。题目题解AtCoder AT_awc0088_a Bus Departure Time题解AtCoder AT_awc0088_b Bus Tour Group Division题解AtCoder AT_awc0088_c Farm Harvest Festival题解AtCoder AT_awc0088_d Control Panel Operation Sequence题解AtCoder AT_awc0088_e Intervals That Can Be Arranged Alternately