RainAir
My OI Blog
RainAir
「CF379D」New Year Letter

题目描述

令 $s_i$ 表示第 $i$ 个字符串,我们有递推式 $s_i = s_{i-2}+s_{i-1}$(其中+ 是将两个字符串拼接起来的符号)
现在需要你构造出长度为 $n$ 的 $s_1$ 和长度为 $m$ 的 $s_2$ ,满足 $s_k$ 中串 AC 作为子串出现了 $x$ 次。
$3 \leq k \leq 50,0 \leq x \leq 10^9,1 \leq n,m \leq 100$

题解

这个题还挺有意思的… dp 可以记录一些状态,不只是记录一个孤零零的值。
首先我们发现最后只需要关心的是 $AB$ 的数量,可能就会想到令 $f_{i}$ 表示 $s_i$ 的 AC 的数量,转移直接 $f_i = f_{i-1}+f_{i-2}$。但这显然不太对,因为中间可能还会拼接起来。
这时候我们的 dp 数组就要多记录点东西了:考虑类似于线段树维护最大字段和那样,$f_i$ 记录一个三元组 $(a,b,c)$ 表示左边的字母是 $a$,AC 的数量为 $b$ ,右边的字母为 $c$ 的数量。拼接的时候只需要看左边字符串的最右端和右边字符串的最左端 更新一下 $b$ 就好了。
然后我们发现 $n,m,k$ 都很小,一个自然的想法是枚举。但是一开始可能会发现枚举要确定头尾是什么字母,还要确定后面会不会和头尾产生新的 AC… 太麻烦了。但是仔细一想可以发现我们其实只需要确定 AC 的个数和头是不是 C,结尾是不是 A 就可以了。这些情况是不会对里面产生影响的,并且产生影响的情况和左右都填其他字母的情况等价。(要不是看了题解发现这种枚举方法我估计就要写大大大分类讨论了 qaq)
然后直接模拟输出就可以了.

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/920
如文中无特殊声明,本文采用 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

「CF379D」New Year Letter
题目描述 令 $s_i$ 表示第 $i$ 个字符串,我们有递推式 $s_i = s_{i-2}+s_{i-1}$(其中+ 是将两个字符串拼接起来的符号) 现在需要你构造出长度为 $n$ 的 $s_1$ 和长度为 $m$ 的 $s_2$ …
扫描二维码继续阅读
2019-10-21
标签
近期评论