【弱省胡策】Round2题解

A.沼跃鱼的FFF

By wyfcyx

来自BZOJ2891,但是上一次AC已经是近两年前,而且多位神犇都是利用随机很多次这种方法过的.

其实这个题很简单.

注意到$n\leq{6}$,显然要在这个上面做文章啦.

令$f[i][j]$表示在前$i$个Po姐参与匹配的情况下,大爷匹配状态的集合为$j$这种情况发生的概率.

何谓匹配状态:就是指一个二进制数,第$i-1$位以0/1表示第$i$个大爷是否在匹配中.

考虑第$i+1$个Po姐,我们可以$O(2^n)$枚举她可以和哪些大爷进行匹配,那么现在的集合会变成什么样子呢?

对于原集合的所有状态,以及现在新增的若干匹配边,若这个状态加上这条匹配边得到的新状态不在原集合中,我们就将这个新状态加入集合.

于是这样的集合数明面看来是$O(2^{2^n})$的,看起来直接要爆炸了.

其实很容易注意到每个大爷只会在第一次出现在匹配边时造成影响,那么有用的信息只有最终所有匹配边中大爷的并集,以及加入大爷的顺序.

于是可用的集合数最多只有$O(n!2^n)$这么多.这样算一下感觉很爆炸,但其实还有很多重复,最坏只有$4000$个状态.

这样简单的dp就可以了.

状态数为$O(n!2^nm)$,转移数为$O(2^n)$,总时间复杂度为$O(n!4^nm)$.

当然需要一些简单的预处理,不过这里就不说了.

http://ch.ezoj.tk/record/45061

B.沼跃鱼的Mushroom

By 18357

1.呵呵。强行分类讨论？

2.呵呵。强行分类讨论？

3.枚举然后判断树同构？

4.枚举然后判断树同构？

5.贪心+贪心。

6.贪心+贪心。

7.贪心+树DP（呃或许说是dfs？）。

8.贪心+贪心。

9-25.膜能写出特判的神犇。

[正解]

我们从深往浅对每一层进行处理，求f(I,j)表示左子树选个节点i，右子树选个节点j，所能得到的最多匹配节点数，这个过程可以用最大费用最大流来求解。

[分值设置]

我觉得出100个点会卡爆CH。就是这样。

[题面思路]

我不认为小丑的盒子、女警豹女的夹子、巴德的坛子等等可以搞成这道题。

其实扎克变成若干块，然后判断扎克同构神马的嘛。呃扎克变500块太可怕了Qwq。

http://ch.ezoj.tk/record/45054

C.沼跃鱼的Password

By jkxing