← 返回题目列表

Codeforces · 2162/B

B. 美丽的绳子

中文机器翻译题面 查看原题

给你一个二进制$$$^{\text{*}}$$$ 字符串$$$s$$$,长度为$$$n$$$。

你的任务是找到 $$$s$$$ 的任意子序列$$$^{\text{†}}$$$ $$$p$$$,使得:

  • 子序列 $$$p$$$ 是 非递减。也就是说,$$$p$$$ 中的每个字符都不大于下一个字符。
  • 让 $$$x$$$ 表示通过以下方式获得的字符串 从 $$$s$$$ 中删除 $$$p$$$ 的所有字符,同时保留剩余字符的顺序。那么 $$$x$$$ 必须是 回文$$$^{\text{‡}}$$$。

您只需要输出满足这两个条件的任何有效子序列$$$p$$$。如果不存在这样的子序列,则输出$$$-1$$$。

请注意,空字符串既是非递减字符串,也是回文字符串。

$$$^{\text{*}}$$$二进制字符串是由字符 ' 组成的字符串0' 和 '1'.

$$$^{\text{†}}$$$A 字符串 $$$s = s_1s_2\ldots s_n$$$ 的 子序列 长度为 $$$m$$$ 的 是一个序列 $$$p = s_{i_1}s_{i_2}\ldots s_{i_k}$$$,使得 $$$1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq n$$$。字符按顺序选择,但不一定是连续的。请注意,空字符串是任何字符串的子序列。

$$$^{\text{‡}}$$$一个字符串 $$$t = t_1t_2\ldots t_m$$$ 是一个 回文 如果对于所有 $$$1 \leq i \leq m$$$,$$$t_i = t_{m - i + 1}$$$。换句话说,字符串向前和向后读起来都是一样的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 3000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10$$$) — 字符串的长度。

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

输出

如果存在解决方案:

  • 在第一行,打印单个整数 $$$k$$$ ($$$0 \le k \le n$$$) — 子序列 $$$p$$$ 的长度。
  • 在第二行,打印 $$$k$$$ 不同的整数 $$$i_1, i_2, \dots, i_k$$$ ($$$1 \le i_1 \lt i_2 \lt \dots \lt i_k \le 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 = \texttt{010}$$$,这是一个回文。

在第二个测试用例中,我们删除 $$$p = \texttt{01}$$$ (索引 $$$2$$$、$$$3$$$),得到 $$$x = \texttt{0}$$$,这是一个回文。

在第三个测试用例中,我们删除 $$$p = \texttt{00111}$$$ (索引 $$$1$$$ 到 $$$5$$$),产生一个空字符串,这通常是一个回文。

在第四个测试用例中,我们删除 $$$p = \texttt{01}$$$ (索引 $$$3$$$、$$$4$$$),得到 $$$x = \texttt{110011}$$$,这是一个回文。

在第五个测试用例中,我们删除 $$$p = \texttt{01}$$$ (索引 $$$5$$$、$$$6$$$),得到 $$$x = \texttt{1001}$$$,这是一个回文。