2025.9.4

由于数据过水，混了个 AK。
T1

https://www.luogu.com.cn/problem/P12779
一个显然的贪心，可以用递归实现。
T2

https://www.luogu.com.cn/problem/P7165
经典思路，枚举断的那条边后考虑另外一条边如何断最优，分为两种情况：

• 祖先，接近 \(\frac{n - siz_u}{2} + siz_u\)。
  
• 子树外非祖先，接近 \(\frac{n - siz_u}{2}\)。
  

于是使用 set 维护上面两种情况，二分找这四种情况即可。
该题耗时过长，主要原因是刚开始少漏了一种情况后实现会比较复杂，发现假了的时候已经过了 1h，好在后面经过调整，迅速得到正确思路。
T3

https://www.luogu.com.cn/problem/P9676
考虑发现如果一个能力在某个时刻变为 \(0\) 了，那这个时刻前的增幅是没有必要的；于是可以不用管对 \(0\) 取 \(\max\) 这个条件，因为最终答案一定不会用到。
于是可以考虑 \(dp_{i, j, x, y}\) 表示第 \(i\) 天选择第 \(j\) 个能力后另外两个能力分别在 \(x, y\) 天前选择时最大总价格，转移是简单的，朴素是 \(O(n^3)\) 的。
但是你注意到连续 \(2x\) 天不选择的代价大概是 \(2x^2\) 级别的，于是顶多 \(2\sqrt{w}\) 天连续不选，否则肯定不优，于是可以做到 \(O(nw)\)。
阈值设的 \(150\)，实际上应该要 \(200\) 才行，但是数据过水，冲过去了；赛时在最后 10min 才做出该题，并没有细想阈值到底取什么，于是胡了一个 \(\sqrt{V}\)，之后时间充足情况下应该尝试进行证明或者进行对拍，像今天不确定阈值取什么又没有时间进行验证的话则在时间范围内尽可能开大，防止出现错误。
T4

https://www.luogu.com.cn/problem/P8421
一个细节较多的数据结构，仔细想好每一步，精细实现。

来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除