Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom6月前

04/24
17:00
trie 树形动规 状压动规 线段树 计算几何

[czyz 2017.04.24 jz 03.08 省选模拟赛]

A:http://czyzuoj.com/problem/95

B:http://czyzuoj.com/problem/96

C:http://czyzuoj.com/problem/97

A:超哥线段树裸题,在雅礼的时候做过

 

B:

考虑把所有串反过来建成一棵trie树,押韵的两个单词在树上肯定是兄弟或者父子,所以弄出来的答案应该是从一个点开始,每次走遍他的兄弟然后往上,直到某个点走遍他的兄弟然后往孩子走,树形dp一下就可以了

 

C:

第i步的时候在一个dep为i的位置打叉肯定是最优的

我们可以证明出当 k*k>=n 的时候是肯定可以在k步内解决的

当k*k<n,即k最大是19的时候,按照dfs序dp,设f[T][mask]表示的是能否用mask去覆盖dfs序前T个dep为k的节点,然后也按照dfs序转移即可

 

[czyz 2017.04.24 jz 03.08 省选模拟赛]