# 「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}<a_{i,2}<\cdots<a_{i,l_i}\le n$；
- 对于任意 $1\le i\le n$，恰好存在一个二元组 $(p,q)$，使得 $a_{p,q}=i$；
- 对于任意 $1\le i\le k$，记字符串 $t=s_{a_{i,1}}s_{a_{i,2}}\ldots s_{a_{i,l_i}}$，则 $t$ 不是回文的。

在此基础上，你需要最大化 $k$ 的值；或者判断不存在一种合法的方案。

特别地，如果 $k$ 的值不是最大的，你也可能获得一定的部分分。

## 输入格式

从标准输入读入数据。

**本题有多组测试数据。** 

输入的第一行包含一个正整数 $c$，表示测试点编号。$c=0$ 表示该测试点为样例。

第二行包含一个正整数 $q$，表示测试数据组数。

对于每组测试数据：

- 第一行包含一个正整数 $n$，表示字符串 $s$ 的长度；
- 第二行包含一个长度为 $n$ 的字符串 $s$。保证 $s$ 中仅包含小写英文字母。

## 输出格式

输出到标准输出。

对于每组测试数据：

- 如果不存在一种合法的方案，输出一行一个字符串 `Shuiniao`；
- 否则，你需要：
  - 在第一行输出一个字符串 `Huoyu`；
  - 第二行输出一个正整数 $k$ $(1\le k\le n)$，表示你划分成的子序列个数；
  - 接下来 $k$ 行，对于第 $i$ 行 $(1\le i\le k)$：
    - 首先输出一个正整数 $l_i$ $(1\le l_i\le n)$，表示第 $i$ 个子序列的长度；
    - 接下来输出 $l_i$ 个正整数 $a_{i,1},a_{i,2},\ldots, a_{i,l_i}$ $(1\le a_{i,j}\le n)$，表示第 $i$ 个子序列。

请注意，你的输出需要满足题目描述中所有的限制，否则，你将会得到 $0$ 分。

## 样例 #1

### 样例输入 #1

```
0
4
4
kdoi
7
ccccccc
7
sszcdjr
7
abacaca
```

### 样例输出 #1

```
Huoyu
2
2 1 2
2 3 4
Shuiniao
Huoyu
3
3 1 2 3
2 4 5
2 6 7
Huoyu
3
2 1 4
3 2 3 5
2 6 7
```

## 提示

**【样例 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 <input-file> <output-file>
```

其中，参数 ` <input-file>` 与 `<output-file>` 依次表示输入文件与你的输出文件。

若你的输出中的数字大小范围不合法，则校验器会给出相应提示并立即退出。否则，校验器输出以下内容：

- 在第 $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` 的检查结果。

## 时空限制



时间限制
1.00s

内存限制
512.00MB

Tags: 洛谷原创, 洛谷月赛, Special Judge, O2优化, 2024
Difficulty: 提高+/省选−