[洛谷P5281][ZJOI2019]Minimax搜索

这个题考试的时候完全没思路,现在想了1h瞬间会70分,然后满分也不难,就是代码难写一点。
首先考虑计算所有能取的方案数。先算出所有初始状态下的值,记$f(x)$为x节点初始状态下的值,$sz(x)$为x节点子树中叶子的个数。
然后从根开始考虑,记$g(x)$为在x的子树中让x节点改变的方案数(包括空集)。对于根来说(暂不考虑叶子),由于所有叶子节点初始值不同,所以只要能让$f(x)$最大的那个儿子改变,那么就是一种合法方案。如果无法让最大的那个儿子改变,那么就要让其他儿子中的任意一个至少大于最大的那个儿子的值。我们不妨记$h1(x,s)$表示令以x为根的子树中最终结果能使x的值大于等于s的方案数。那么设根为rt,最大的那个儿子为p,有:
$g(rt)=g(p)2^{sz(rt)-sz(p)}+(2^{sz(p)}-g(p))(2^{sz(rt)-sz(p)}-\displaystyle\prod_{y\in son(x),y\not =p} (2^{sz(y)}-h1(y,f(p)+1))$
那么对于其他的$g$的转移和这个类似(对于叶子节点需要特判),如果要取$min$的话,是要最小的那个儿子改变,或者存在一个其他的比最小的小,这样我们又需要记一个$h2(x,s)$表示以x为根的子树中最终结果能使x的值<=s的方案数。
那么考虑$h1$和$h2$的转移,由于对称性,不妨只考虑一个。
对于$h1(x,s)$(叶子节点特判,暂不考虑),如果该点要取max,那么:
$h1(x,s)=2^{sz(x)}-\displaystyle\prod_{y\in son(x)} (2^{sz(y)}-h1(y,s))$
否则如果该点要取min,那么:
$h1(x,s)=\displaystyle\prod_{y\in son(x)} h1(y,s)$
可以发现,每个点只需要遍历一次,只会用到$g$,$h1$,$h2$中的某一个,而且如果是$h1$或$h2$的情况,第二个参数对于每个点来说是固定的。
所以我们可以$O(n)$求出所有能使根改变的方案。
50分到手。
然后我们可以在dp的时候再加一个$w(S)$的限制,同样的方法可以得到$w(S)$不超过某个值的方案数。
处理一下就70分到手了。

对于100分做法,可以发现所有的转移对于其任意一个儿子来说都是一次函数,所以可以用动态dp来处理这个问题。可以使用静态AAA树来进行ddp,时间复杂度$O(n\lg n)$。代码感觉比较难写,因为每个点的转移有三种情况。

Tagged with:

发表评论