March - May 做题合集

「省选联考 2024」迷宫守卫

首先考虑是最大化字典序，因此按位贪心。

考虑第一位怎么求。有一个简单的做法就是二分，然后转换成 \(0\)/\(1\) 然后 dp。就是令 \(f_{u,0/1}\) 表示让 u 这个点开始，走的第一个叶子最优是 \(0\)/\(1\) 的最小花费。然后再判断是否小于等于 \(k\)。

这个做法怎么扩展呢？

可以考虑把让第一位最优的最优决策（花费最小）保留下来，然后模拟 Bob 的行走，来判断 Bob 第二位的最优结果。

这个时候 Bob 是从一个节点回溯上来，要到另一个还没有涉足过的子树。

那么我们其实完全可以把将要前往的一棵子树内的决策清空，然后再算这个子树的最优决策。

发现这个做法有点问题。如果我们从 \(u\) 走到 \(u\) 的某个子树，那么 \(u\) 这个点的决策有可能改变。所以我们就枚举 \(u\) 这个点的决策，然后再暴力计算子树内的决策。

这样就做完了。时间复杂度 \(O(2^nn^2)\)。然而其实二分 dp 可以换成更好的做法，把复杂度降到 \(O(2^nn)\)。

「JOISC 2019」時をかけるビ太郎

口胡。

首先相邻两个区间不交是极其简单的。随便讨论就可以了。

然后发现一段有交的区间等价于它们的交。于是直接把有交的区间缩成它们的交，然后转化成上面的情况，线段树随便做做就完事了。