RainAir
My OI Blog
RainAir
「CF1110H」Modest Substrings

好久不更博了~~~

题目大意

定义一个数是好的当且仅当这个数 $x$ 满足 $l \leq x \leq r$

定义一个长度为 $n$ 的字符串的价值是所有好的数在这个字符串的出现次数的和。

现在给你 $l,r,n$ 让你构造出满足价值最大的情况下字典序最小的串。

$1 \leq l \leq r \leq 10^{800},1 \leq n \leq 2000$

题解

3500的题一看我就做不来。。
首先我们考虑如果 $r-l$ 比较小怎么办。
一个很显然的想法是将所有的数字暴力建 AC 自动机,然后 dp。
设 $f[i][j]$ 表示填了前 i 位,当前状态为 $j$ 的方案数。预处理 $g_i$ 表示 $i$ 状态能对答案造成的贡献。
求 $g_i$ 只需要把 fail 树建出来,然后求每个点到根的 $g$ 的和就可以了。
然后 $f[i][j] * g[ch] \to f[i+1][ch]$ 转移一下就好了。
现在考虑这个极其繁琐的限制 $l \leq x \leq r$。
想一想,我们如果暴力建出来 trie 树,这个树的形态会是一堆满 $10$ 叉子树,我们可以考虑压缩掉这些满 $10$ 叉子树。我们类比数位 dp 中卡上下界的方法,只需要把刚好“脱离”上下界的那些串建出来就好了。
于是我们现在设 $g[i][j]$ 表示第 $i$ 个点(按照未压缩树结构)继续走 $j$ 步对答案的贡献。然后更新一下就好了,最后转移是 $f[i][j] * \sum_{k=0}^{n-i-1}g[ch][k]\to f[i+1][ch]$
然后只需要前缀和优化一下就能快速转移了。

代码

总结

  1. trie 树满叉结构是可以优化掉的。
  2. 一般的这种 dp 还可以考虑加入每个点的贡献,每个结束点都会对 fail 树的子树有贡献。
  3. 我太菜了,活该 pupil
赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/970
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF1110H」Modest Substrings
好久不更博了~~~ 题目大意 定义一个数是好的当且仅当这个数 $x$ 满足 $l \leq x \leq r$ 定义一个长度为 $n$ 的字符串的价值是所有好的数在这个字符串的出现次数的和。 现在给你 $l,r…
扫描二维码继续阅读
2020-01-27
标签
近期评论