NFLSPC #1 K题 String 题解

2018-12-11 21:28:33 By djq_cpp

算法一

考虑子任务1。

此时,字符集$\sigma$上只有一个长度为n的字符串。

易证:若n为奇数,则答案为0;若n为偶数,则答案为1。

时间复杂度:$O(1)$ 期望得分:$5$分

算法二

考虑子任务2。

题目的限制条件较强。所以瞎暴力、随便加些优化就可以通过。

时间复杂度:$O(ans)$ 期望得分:$15$分

算法三

考虑子任务4。

对于一个字符串,定义性质$P$为它能通过若干次操作得到空串。

不难发现一个字符串符合性质$P$当且仅当以下有至少一条满足:

  1. 它是空串;

  2. 它首尾字母相同且去掉首尾后的字符串符合性质$P$;

  3. 它可由两个非空且符合性质$P$的串拼接而成。

我们令$dp0[i]$表示长度为$i$且符合性质$P$的字符串个数、$dp1[i]$表示长度为$i$、符合性质$P$且以上三条中仅满足第(2)条的字符串个数并互相转移。

易得$dp0[i]$可从$dp0[i-j] * dp1[j]$转移而来。

对于$dp1[i]$,考虑用所有满足性质(2)减去同时满足(2)(3)的。前者为$m * dp0[i-2]$、后者为$(1/m) * dp1[j] * dp1[k] * dp0[i-j-k]$的总和。

答案即dp0[n]。

注意所有有效状态的下标均为偶数,故实际数据规模只有n的一半。

时间复杂度$O(n^3)$,期望得分$30$分,结合算法一共$35$分。

算法四

考虑子任务3、5。

在算法三的基础上,对每个$k$记录$dp1[i] * dp1[j] [i+j==k]$的总和。

时间复杂度$O(n^2)$,期望得分$65$分,结合算法一共$70$分。

算法五

考虑子任务8。

使用算法四的方法在本机上跑一分钟并特判数据、直接提交。

时间复杂度O(1),期望得分$5$分,结合算法四共$75$分。

算法六

将上述dp写成生成函数的形式,即

$P0 = P0 * P1 + 1$

$P1 = m * x * P0 - (1/m) * P1^2 * P0$

利用多项式球逆和开方解出P0。

时间复杂度$O(n log n),期望得分$100$分。

算法七

考虑算法三中的三个条件,发现性质P与括号序列的性质类似。

显然,我们可以将字符串上的每个字符上标注$"("$或$")"$,使得整个原串的标注是一个合法括号序列。

不过,一个字符串对应的括号序列可能有多个(如$"aaaa"$可对应$"(())"$或$"()()"$)。在此情况下,我们认为该字符串对应的括号序列为字典序最大的那个。(注意$")" > "("$)这样,对于每个符合性质$P$的字符串,就有且仅有一个括号序列与之对应了。

那么对于每个括号序列,有多少字符串与之对应呢?不妨将其想象成括号序列的染色。简单起见,我们只考虑首尾括号相匹配的括号序列。

对于这些括号序列,它们最外层的括号有$m$种颜色可染、其余每层括号都恰有$m-1$中颜色可染:每个括号都不能与直接包含它们的括号染同一种颜色。

因此,任何长度为$2n$且首尾括号匹配的的括号序列都有$m * (m-1)^{n-1}$种染色方式。

进一步地,所有长度为$2n$且首尾括号匹配的括号序列的总染色数为$C(n-1) * m * (m-1)^{n-1}$,其中$C(n)$表示卡特兰数,即长度为$2n$的括号序列数。

显然,每个符合性质$P$的字符串都可以唯一分解成若干个与首尾括号相匹配的括号序列对应的字符串。

因此,对上面的式子做一次完全背包,就是题目所求的答案。

时间复杂度$O(n^2)$,期望得分$65$分,结合算法一共$70$分。

算法八

使用多项式球逆或分治FFT实现完全背包。

时间复杂度$O(n log n)$或$O(n log^2 n)$, 期望得分$100$分。

算法九

考虑算法六中的方程组,暴力解并使用二项式定理展开,得到一个非常优美的式子(详见本题的最快提交)。

时间复杂度$O(n log n)$或$O(n)$(线性逆元),期望得分$100$分。

*算法十

使用zzq博客的方法优化算法九,时间复杂度$O(sqrt(n) log (n))$。

评论

avatar
20150332
zzq博客有链接吗?能发一个吗?
avatar
wxh010910
这题好像之前被人出过了...而且之前的版本是1e7...做法有组合意义的

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。