P11190 「KDOI-10」反回文串
题目背景
[English Statement](https://www.luogu.com.cn/problem/T519008). You must submit your code at the Chinese version of the statement.
**本场比赛所有题目从标准输入读入数据，输出到标准输出。**
题目描述
我们称一个长度为 $m$ 的字符串 $r$ 是回文的，当且仅当 $r_i=r_{m+1-i}$ 对所有 $1\le i\le m$ 均成立。
给定一个长度为 $n$ 的字符串 $s$，你需要把 $s$ 分成若干个非空子序列，使得每一个子序列都**不是**回文的，并最大化划分成的子序列数。
形式化地说，你需要给出一组序列 $(a_1,a_2,\ldots,a_k)$，满足：
- 对于任意 $1\le i\le k$，记 $l_i$ 为 $a_i$ 的长度，则 $l_i\ge 1$，且 $1\le a_{i,1}
输入格式
无
输出格式
无
说明/提示
**【样例 1 解释】**
对于第一组测试数据，显然输出构成一个合法的子序列划分，并且
- 对于第一个子序列，$t=\tt{kd}$ 不是回文的；
- 对于第二个子序列，$t=\tt{oi}$ 不是回文的。
故这是一组合法的输出。可以证明，对于这组测试数据，$2$ 是 $k$ 的最大可能值。
对于第二组数据，它的任意一个子序列都是回文的， 故显然不存在合法的划分方案。
**【样例 2】**
见选手目录下的 `anti/anti2.in` 与 `anti/anti2.ans`。
这个样例共有 $10$ 组数据，均满足 $n=1\,000$。其中第 $1\sim 3$ 组数据满足特殊性质 A，第 $4\sim 6$ 组数据满足特殊性质 B。
***
**【评分方式】**
本题共有 $20$ 个测试点，每个测试点满分 $5$ 分。
本题采用自定义校验器（special judge）评测。每组测试数据可能有多组解，你只需要给出**任意**一组。
在每个测试点中，你的得分是在所有测试数据上得分的最小值。对于每组测试数据：
- 如果你错误地判断了是否有解或者给出了一组不合法的序列，你将会获得 $0$ 分；
- 如果你正确判断了是否有解，并在有解时给出了一组合法的序列：
- 如果 $k$ 的值不是最大的，你将会获得 $2$ 分；
- 如果 $k$ 的值是最大的，你将会获得 $5$ 分。
***
**【数据范围】**
对于全部的测试数据，保证：
- $1\le q\le 10$；
- $1\le n\le 10^5$；
- $s$ 中仅包含小写英文字母。
|测试点|$n\le$|特殊性质|
|:--:|:--:|:--:|
|$1,2$|$5$|无|
|$3\sim 5$|$18$|无|
|$6\sim 8$|$1\,000$|B|
|$9\sim 11$|$1\,000$|无|
|$12\sim 14$|$10^5$|A|
|$15\sim 17$|$10^5$|B|
|$18\sim 20$|$10^5$|无|
- 特殊性质 A：保证 $n$ 是偶数，且 $s$ 中每个字符的出现次数都不超过 $\frac{n}{2}$；
- 特殊性质 B：保证 $s$ 中仅有 `a` 和 `b`。
***
**【如何使用校验器】**
为了方便选手测试，在附件的 `anti` 目录下我们下发了 `checker.cpp` 文件作为样例校验器，选手可以编译该程序，并使用它校验自己的输出文件的结果是否**合法**。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。
编译命令为：
```sh
g++ -o checker -std=c++14 -O2 checker.cpp
```
`checker` 的使用方式为：
```sh
checker
```
其中，参数 ` ` 与 `` 依次表示输入文件与你的输出文件。
若你的输出中的数字大小范围不合法，则校验器会给出相应提示并立即退出。否则，校验器输出以下内容：
- 在第 $i$ 行 $(1\le i\le q)$ 中，输出第 $i$ 组测试数据的详细提示信息；
- 在第 $(q+1)$ 行，输出这个测试点的总结信息。
例如，对于样例 1 的输入与输出，校验器将会向屏幕打印如下内容：
```plain
Test case 1: OK. Participant's answer is YES (Huoyu), and k=2.
Test case 2: OK. Participant's answer is NO (Shuiniao).
Test case 3: OK. Participant's answer is YES (Huoyu), and k=3.
Test case 4: OK. Participant's answer is YES (Huoyu), and k=3.
ok 4 / 4 test cases passed. (4 test cases)
```
若将输出改为如下：
```plain
Huoyu
2
2 1 2
2 3 4
Huoyu
1
7 1 2 3 4 5 6 7
Huoyu
3
3 1 2 3
2 4 5
2 6 7
Huoyu
3
2 1 4
3 2 3 5
2 6 7
```
则会向屏幕打印如下内容：
```plain
Test case 1: OK. Participant's answer is YES (Huoyu), and k=2.
Test case 2: Wrong answer. The string t obtained in the subsequence a[1] is palindrome.
Test case 3: OK. Participant's answer is YES (Huoyu), and k=3.
Test case 4: OK. Participant's answer is YES (Huoyu), and k=3.
wrong answer 3 / 4 test cases passed.
```
**请注意：** 样例校验器只会检查你的输出是否合法，而**不会**：
- 检查有解性是否判断正确；
- 检查 $k$ 是否被最大化。
例如，将样例 1 的输出改为如下：
```plain
Shuiniao
Shuiniao
Shuiniao
Shuiniao
```
此时，样例校验器仍会返回 `ok` 的检查结果。