题目描述

给定一个长度为 $n$ 的二进制字符串 $s$。

你的任务是找到 $s$ 的一个子序列 $p$，满足以下条件：

• 子序列 $p$ 是非递减的。即 $p$ 中每个字符都不大于其下一个字符。
• 设 $x$ 表示从 $s$ 中移除 $p$ 的所有字符后（保持剩余字符的顺序）得到的字符串。则 $x$ 必须是回文串。

你只需要输出任意一个满足条件的子序列 $p$。如果不存在这样的子序列，输出 $-1$。

注意，空串既是非递减的，也是回文串。

二进制串是只包含字符 ‘0’ 和 ‘1’ 的字符串。

字符串 $s = s_1s_2\ldots s_n$ 的子序列是 $p = s_{i_1}s_{i_2}\ldots s_{i_k}$，其中 $1 \leq i_1 < i_2 < \ldots < i_k \leq n$。字符按顺序选取，但不要求连续。空串也是任何字符串的子序列。

对于字符串 $t = t_1t_2\ldots t_m$，若对所有 $1 \leq i \leq m$，都有 $t_i = t_{m - i + 1}$，则 $t$ 是回文串。也就是说，这个字符串从前往后和从后往前读相同。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 3000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10$），表示字符串的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $s$。

输出格式

如果存在满足条件的解：

• 第一行输出一个整数 $k$（$0 \leq k \leq n$），表示子序列 $p$ 的长度。
• 第二行输出 $k$ 个不同的整数 $i_1, i_2, \dots, i_k$（$1 \leq i_1 < i_2 < \dots < i_k \leq n$），表示 $s$ 中构成 $p$ 的字符下标（按其在 $s$ 中出现的顺序）。

否则，输出一行 $-1$。

样例

5
3
010
3
001
5
00111
8
11010011
6
100101

0

2
2 3
5
1 2 3 4 5
2
3 4
2
5 6

样例说明

在第一个测试用例中，选择空子序列，得到 $x = 010$，它是回文串。

在第二个测试用例中，移除 $p = 01$（下标 $2, 3$），剩下 $x = 0$，它是回文串。

在第三个测试用例中，移除 $p = 00111$（下标 $1$ 到 $5$），剩下空串，空串本身是回文串。

在第四个测试用例中，移除 $p = 01$（下标 $3, 4$），剩下 $x = 110011$，它是回文串。

在第五个测试用例中，移除 $p = 01$（下标 $5, 6$），剩下 $x = 1001$，它是回文串。

由 ChatGPT 5 翻译

来源

Codeforces 2162B，英文题名 Beautiful String。