B4520 [科大国创杯小学组 2026] 好串串

民间数据

快要小学毕业的小可可决定给好朋友小果果送毕业礼物。 现在小可可有一个长度为 $n$ 的小写字符串 $S$。 规定“好串串”是指前一半字典序单调不降、后一半字典序单调不升的回文串。 形式化地，长度为 $m$ 的“好串串” $S$ 满足： * $S_1 \le S_2 \le \dots \le S_{\lceil \frac{m}{2} \rceil}$， $S_{\lceil \frac{m}{2} \rceil} \ge S_{\lceil \frac{m}{2} \rceil + 1} \ge \dots \ge S_m$； * 对于所有 $i = 1, 2, \dots, m$，满足 $S_i = S_{m-i+1}$。 > 字典序是指小写字母表中的顺序（`a` 最小 `z` 最大）；$\lceil \frac{m}{2} \rceil$ 是指 $\frac{m}{2}$ 上取整。 如 `z`，`bbb`，`accgcca`，`ccdeeedcc`，`ghg` 等是“好串串”；`acbca`，`syzzh`，`ccb` 等不是“好串串”。 现在小可可要把 $S$ 分割成若干个**不相交**的“好串串”送给小果果。因为小果果不想让书包里堆满“好串串”，所以小可可要让分割出的“好串串”个数尽量少。 可是小可可不会分割，请你来告诉她**最少**能分割成多少个“好串串”吧！

**本题多组测试。** 第一行两个正整数 $C, t$，表示测试点编号和数据组数，对于样例 $1$ 满足 $C=0$。 接下来 $t$ 行，每行一个小写字符串 $S$，表示小可可的字符串。

输出包含 $t$ 行，每行一个正整数，表示这组数据的答案。

#### ****样例解释**** * 对于第一组测试数据，可以分割为 `czc` 和 `cc`。 * 对于第二组测试数据，可以分割为 `a`, `b`, `aba` 或 `aba`, `b`, `a`。 #### ****其它样例说明**** * **样例 2 ~ 7**：见选手目录下的 `string/string*.in` 与 `string/string*.ans`。样例中的 $C$ 代表这组样例对应的实际测试点，其数据范围一致。 | 样例编号 | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | $C$ | $2$ | $4$ | $8$ | $13$ | $16$ | $17$ | #### ****数据范围**** 下文中 $N$ 表示单组测试点中所有测试数据 $n$ 的总和。 对于所有测试数据，均有输入的数字均为正整数， $t \le 100$，$n \le 5 \times 10^6$，$N \le 1 \times 10^7$ 且串 $S$ 仅包含小写字母。 | 测试点编号 | $n \le$ | $N \le$ | 特殊性质 | | :---: | :---: | :---: | :---: | | $1$ | $5 \times 10^6$ | $1 \times 10^7$ | A | | $2, 3$ | $10$ | $20$ | 无 | | $4 \sim 7$ | $200$ | $500$ | 无 | | $8 \sim 12$ | $5000$ | $5 \times 10^4$ | 无 | | $13 \sim 15$ | $5 \times 10^6$ | $1 \times 10^7$ | B | | $16$ | $5 \times 10^6$ | $1 \times 10^7$ | C | | $17 \sim 20$ | $5 \times 10^6$ | $1 \times 10^7$ | 无 | * 特殊性质 A：满足 $S$ 全为字符 `a`。 * 特殊性质 B：满足 $S$ 中不存在任意两个相邻字母相同。 * 特殊性质 C：满足 $S$ 随机生成，且 $t=2$。