做题记录 #4：The 2025 ICPC Asia Yokohama Regional Contest
:::align{center}
\color{Black}\textsf{The 2025 ICPC Asia Yokohama Regional Contest}
:::
:::align{center}
\color{Green}\textsf{\textbf{[A] Tatami Renovation}}
:::
- 标签：蓝，离散化，贪心，DP。
- 解法：先奇偶分开进行一下离散化，之后对于可能出现的每种形态进行分类讨论得出一种贪心策略，归纳即可得出结论正确性，时间复杂度
O(n\log n) 。
:::align{center}
\color{Green}\textsf{\textbf{[B] Minimizing Wildlife Damage}}
:::
- 标签：黑，DP，贪心，二分，凸包，平衡树。
- 解法：考虑将最终得出的序列分为三部分，第一部分必然形如一个最大独立集（被野猪拱完了），第二部分的每个元素都被野猪供了一些（即全部
-\Delta ），第三部分没有受到影响。对于每个询问，离线下来，二分出第一与第二部分最优的分割点（最多两个），右边的贡献形如一个一次函数，倒着扫用平衡树维护凸包即可。边界要讨论清楚，令n,m 同阶，时间复杂度O(n\log n) 。
:::align{center}
\color{Green}\textsf{\textbf{[C] Seagull Population}}
:::
- 标签：蓝，贪心，构造。
- 解法：有一种比较简单的贪心策略，把序列中所有元素减去全局最小值，就变成了经典问题铺设道路。但是这个策略有一些问题，问题就在于减去最小值时，底下的那些段可以割开，进而合并上面的同层连续段。分析答案下界之后可知最优性。时间复杂度
O(n\log n) 。
:::align{center}
\color{Green}\textsf{\textbf{[D] Decompose and Concatenate}}
:::
- 标签：橙，贪心，分类讨论。
- 解法：直接分类讨论进行贪心即可，注意边界情况要讨论清楚。
:::align{center}
\color{Green}\textsf{\textbf{[E] Cutting Tofu}}
:::
- 标签：黄，数学，二分。
- 解法：显然其中某一维会“顶满”，枚举这一维，做一个二分，就可以求出答案。时间复杂度
O(t\log V) 。
:::align{center}
\color{Gray}\textsf{\textbf{[F] Astral Geometry}}
:::
待更新。
:::align{center}
\color{Green}\textsf{\textbf{[G] Charity Raffle}}
:::
- 标签：紫，组合数学。
- 解法：先转换成计数不合法的方案，能得到一种特定的序列形态。对这个序列的某些元素
-1 ，可以得到一个双射：答案形如计数长度为n 、值域为[1,m] 、总和为s 的整数序列，直接容斥做，令n,k,m 同阶，时间复杂度O(n+\log P) 。
:::align{center}
\color{Green}\textsf{\textbf{[H] U-Shaped Panels}}
:::
- 标签：黄，贪心。
- 解法：直接从左上往右下贪心地对图形进行 match，正确性显然——若有多种可能的形态，那么必然无解。时间复杂度
O(tnm) 。
:::align{center}
\color{Green}\textsf{\textbf{[I] Game of Names}}
:::
- 标签：绿，博弈论，分类讨论。
- 解法：把连续段分离，对于每个段分长度奇偶和两边元素讨论答案，发现只有最靠近左右两边的段可能是非平凡的。最后把两位选手的得分相加后进行比较。时间复杂度
O(tn) 。
:::align{center}
\color{Green}\textsf{\textbf{[J] ICPC Board}}
:::
- 标签：绿，分类讨论，构造。
- 解法：对于较小的 case 考虑，发现合法的图案并不多，直接对于每行 / 每列枚举特殊形态并尝试 match。时间复杂度
O(tnm) 。
:::align{center}
\color{Gray}\textsf{\textbf{[K] Membership Structure of a Secret Society}}
:::
待更新。
:::align{center}
\color{Gray}\textsf{\textbf{[L] Common Tangent Lines}}
:::
待更新。