哈希 + 二分 + DP

首先看到题面，很容易想到一个$DP$，令$f[i]$为划分到$i$为止的方案数。

然后朴素的暴力转移是$O(n^2)$的，非常显然一个状态$i$能够转移到的$j$是一段连续的，进而想到使用前缀和优化。

又双叒叕是题外话

今天模拟考是原题大战。

$T1​$是这题。
$T2$是某次$CF\ Div1\ E$题。
$T3​$反正是某道神仙题。

像我这样的菜鸡只能来做做相对可做的T1

虽然只是相对可做但是还是被全场切穿了啊喂

内心OS：这个不订正的理由真的nice

对于这题，看到字符串匹配，第一反应想到字符串hash，同时看到$len \leq 8 $ ，考虑对于先给出的$n$个字符串，$O(len^2)$枚举它的子串，将其加入$map$中，但是要注意如果一个然后对于每个字符串，我们都统计一下它最后一次出现在哪里（于是就可以顺便判一下重）

然后我们在询问的时候，就可以直接输出这个字符串对应的出现次数以及最后一处出现的位置啦QwQ

首先我作为一个蒟蒻，拿到字符串题，首先看看能不能无脑哈希

然后于是我们就发现了一个绝妙的做法：暴力枚举每个字符串能够转换成的字符串

于是我们就获得了$O(N * 8^4)$的优秀复杂度

显然会T飞QwQ

我们考虑再这个基础上进行优化

STL大法好！

（看到楼下的大佬们都没有用我这个方法，我就来脱碳甲醛一下辣~~）

以上都是废话

我所说的这个方法，具体思路是这样的：

• 最首先，基础的并查集大家应该都会，如果不会的话可以看代码或者出门右转P3367并查集模板
• 然后，STL中的Map可以直接方便地解决字符串哈希的问题
• 但是，每次都用一遍Map似乎显得有些不优美，似乎有些慢的说
• 所以，我们需要引进两个数组，一个Num和一个Names
• Num是一个Map，它的作用就是Num[“A”]表示名为A的人的编号
• 于是，Names就是反过来的Num，Name[i]表示编号为i的人的名字
• 总体而言，不仅加快了速度，还方便了调试