做题记录 #3：The 2025 ICPC AEC Online Contest (I)
:::align{center}
\color{Black}\textsf{The 2025 ICPC AEC Online Contest (I)}
:::
:::align{center}
\color{Green}\textsf{\textbf{[A] Who Can Win}}
:::
- 标签：黄，模拟。
- 解法：直接模拟，考虑每位选手最好情况和最坏情况的过题数和罚时，如果某位选手的最好情况能好于其他所有选手的最坏情况，那么就可能成为答案。
:::align{center}
\color{Green}\textsf{\textbf{[B] Creating Chaos}}
:::
- 标签：橙，数学。
- 解法：直接输出
1\sim k 就是最优的。
:::align{center}
\color{Green}\textsf{\textbf{[C] Canvas Painting}}
:::
- 标签：绿，贪心，优先队列。
- 解法：首先只会合并相邻的颜色，把区间从
[l,r] 转换成[l,r) ，就是优先队列经典贪心，时间复杂度O(n\log n) 。
:::align{center}
\color{Green}\textsf{\textbf{[D] Min-Max Tree}}
:::
- 标签：绿，树形 DP。
- 解法：对于极差问题有一个很经典的 trick 就是钦定
-1/0/1 的系数，f_{u,-1/0/1} 表示u 子树内目前的系数和是-1/0/1 ，转移非常简单。
:::align{center}
\color{Gray}\textsf{\textbf{[E] tetrart}}
:::
待更新。
:::align{center}
\color{Green}\textsf{\textbf{[F] Robot}}
:::
- 标签：紫，交互，博弈论。
- 解法：考虑在机器人右上角划出一个正方形把它围住，之后横竖交替切，最多操作是
5n ，n 为正方形边长。但是发现直接堵墙机器人跑得很快，隔一格放一个也拦不住，于是考虑隔三个放一个，机器人走近了再细致地堵。实测取n=157 可以通过。
:::align{center}
\color{Green}\textsf{\textbf{[G] Sorting}}
:::
- 标签：橙，图论。
- 解法：连边后判断拓扑序是否唯一即可。
:::align{center}
\color{Green}\textsf{\textbf{[H] Walk}}
:::
- 标签：紫，网络流。
- 解法：考虑最小割。一条路径会把左上角和右下角割开，对于矩形的限制只需要在初始图的基础上，将矩形的左下角和右上角连边，正反各一条，一条流量为
a_i ，一条流量为b_i 。直接跑就能过。
:::align{center}
\color{Green}\textsf{\textbf{[I] Knapsack Problem}}
:::
- 标签：黄，最短路。
- 解法：注意到正着反着走答案是一样的。做类似最短路的东西，记
f_u 表示到了u 结点用了几个背包、装了多少物品。
:::align{center}
\color{Green}\textsf{\textbf{[J] Moving on the Plane}}
:::
- 标签：蓝，计数，容斥。
- 解法：先曼哈顿距离转切比雪夫距离，之后
x,y 两维分开做。限制转换为了x,y 的极差\le k ，直接暴力枚举这一段在哪里，用组合数可以轻松地算贡献，时间复杂度O(NMK) 。
:::align{center}
\color{Gray}\textsf{\textbf{[K] Counting}}
:::
待更新。
:::align{center}
\color{Gray}\textsf{\textbf{[L] cover}}
:::
待更新。
:::align{center}
\color{Green}\textsf{\textbf{[M] Teleporter}}
:::
- 标签：蓝，最短路，换根 DP。
- 解法：先建出分层图，单层之内的正着倒着做两遍 dfs 转移即可，时间复杂度
O(nm) 。