这是毕克好久之前讲过的题……当时没写,现在再看到,回忆起做法就写了一发。
题意简述
定义长度为 $n$(奇数)的 01
字符串是好的,当且仅当可以通过进行 $\frac{n - 1}{2}$ 次下面的变换,使得最后字符串变为 1
。
变换是选择一个长度为 $3$ 的字串,将其改为这 $3$ 个字符的众数(即每次操作会减少 $2$ 个字符)。
先有一个字符串 $S$ ,保证长度为奇数,只含有 0
, 1
, ?
。分别将每个 ?
改为 0
与 1
中的一种,问有多少种方案,使得字符串是好的。
$1\le |S|\le 3\times 10^5$ 。
主要思路
可以发现,如果在字符串后面加入一个字符,某些操作是不劣的。比如 000
肯定先变成 0
,011
或 101
肯定先变成 1
。
然后我们可以构造出如下的自动机。
至于为啥 11
只加一个字符就可以再次变为 11
,你可以理解为 11
后面无论加入什么,最后总是好的。
然后就可以倒着 dp 了。
参考代码
1 |
|