首页 > 题解 > bzoj 1559 [JSOI2009]密码

bzoj 1559 [JSOI2009]密码

Description

Input

Output

Sample Input

10 2

hello

world

Sample Output

2

helloworld

worldhello

HINT

题解

输出方案太恶心了。

发现n很小,考虑状压。

首先对于所有串建个ac自动机。f[i][j][k]表示长度为i,ac自动机的j节点,当前串的状态为k(二进制),按照往儿子走的顺序转移下、

最后结果是f[len][1..sz][(1<< n)-1]求和

发现空间不够,第一维滚动一下。。

发现输出方案的答案是42。可以观察一下,对于所有s1+a..z+s2的这种组合,方案数肯定是大于42的(a..z可以换位置,还是合法的)

那么一开始就去掉所有串包含串的情况(子串),那么最后就是这些串的紧密全排列。(还要考虑一个串的后缀是另一个串的前缀的情况。。)

反正这个暴力非常难写。。hdu有个不输出方案的,实在懒得写就去搞那个吧。

(hdu2825,要求有至少k个串是子串,就是最后统计答案的时候判下二进制位数是不是多于k就好了。。这题我常数写崩了,被卡常,但是对拍没问题,就不往上放了。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×