当前位置:首页 > 搜索 > 记忆化搜索 > 正文
洛谷P8256字符串[NOI Online 2022]
841+

题目大意:给定一个仅包含01-的字符串,对于每个字符,如果是数字,则放入新字符串的末尾,否则删除新字符串的开头或者结尾,请问有多少种方案可以得到字符串t?

题目描述

Kri 非常喜欢字符串,所以他准备找 $t$ 组字符串研究。

第 $i$ 次研究中,Kri 准备了两个字符串 $S$ 和$R$ ,其中 $S$ 长度为 $n$,且只由 `0`, `1`, `-` 三种字符构成(注:这里的第三种字符是减号),$R$ 初始时为空。

每次研究,Zay 会带着一个美丽的长度为 $m$ 的字符串 $T$ 来找 Kri 玩,Kri 非常羡慕 Zay 拥有如此美丽的字符串,便也想用字符串 $S$ 和 $R$ 变出字符串 $T$。

具体地,Kri 将会进行 $n$ 次操作。每次操作中,Kri 会取出 $S$ 的第一个字符(记为 $c$),并将其从 $S$ 中删去。如果 $c = \texttt{-}$,则 Kri 要删去 $R$ 的开头字符或结尾字符(数据保证删去后 $R$ 不为空)。否则,Kri 会将 $c$ 加入到 $R$ 的末尾。

当进行完所有操作后,Kri 会检查 $R$ 是否和 $T$ 相等。如果 $R = T$,Kri 就会感到开心;否则,Kri 会感到难受。

请问在每次研究中,Kri 有多少种操作方式使自己最后感到开心?我们定义两种方案不同,当且仅当在某种方案的某次操作中, Kri 删去了 $R$ 的开头字符。而在另一种方案的这次操作中, Kri 删去了 $R$ 的结尾字符。

由于答案可能很大,你只需要输出答案除以 $1,000,000,007$(即 $10^9+7$)的余数。

输入输出格式

输入格式

第一行一个正整数 $t$。

接下来有 $t$ 组数据分别表示 $t$ 次字符串的研究,对于每组数据:

第一行有两个正整数 $n,m$,分别表示字符串 $S,T$ 的长度。

第二行是字符串 $S$。

第三行是字符串 $T$。

输出格式

共 $t$ 行,第 $i$ 行表示第 $i$ 组研究的答案。

输入输出样例

输入样例 #1

3
6 2
10-01-
01
7 3
010-1-1
101
6 4
111-00
1100

输出样例 #1

2
1
2

输入样例 #2

见附件中的 string2.in

输出样例 #2

见附件中的 string2.out

说明

**【样例 1 解释】**

对于第一组数据,有以下两种方案:

– 第一个 `-` 删 $R$ 的开头,第二个 `-` 删 $R$ 的结尾。
– 第一个 `-` 删 $R$ 的结尾,第二个 `-` 删 $R$ 的开头。

**【数据范围】**

对于 $20\%$ 的数据,$n,m\le 15$。

对于 $30\%$ 的数据,$n,m\le 30$。

对于 $70\%$ 的数据,$n,m\le 80$。

对于另 $10\%$ 的数据,保证答案不超过 $1$。

对于 $100\%$ 的数据,$1\le t\le 5$,$1\le n,m\le 400$。

解题思路

30分:暴力枚举遇到-的时候,是删除开头还是结尾,最后验证字符串是否一样。

70分:记忆化,记录处理到第k个字符,当前字符串是什么,后面匹配成功的方案数。

100分:当前字符串种类很多,无法全部记忆化,考虑他跟字符串t的关系。

对于新加入的字符,如果他跟字符串t能从头开始匹配,那么可以选择留着它(永不删除),或者选择删除它,可以从左边删除或者右边删除。如果从左边删除,那么当前的所有字符都必须从左边删除,不能存在永不删除和右边删除;如果是右边删除,不入队即可,记录右边删除次数。如果是永不删除,那么它跟之前永不删除的字符串接在一起,必须是t的前缀,且不能存在右边删除,因为它是新的右端。(感谢qzm123提供思路)

对于-号,要么删除左边,要么删除右边,前提是之前积累了删除的字符。

程序实现

dfs参数解释:k表示执行到第k个字符 、第k个操作;c表示有c个字符是永不删除的,他们跟字符串t的前缀可以匹配成功;x表示前k个字符中,有x个01在左边被删除;y表示有y个01在右边被删除。

About

坚决不Copy代码!

本文标签:,,,,,,,,,

报歉!评论已关闭.