← 返回题目列表

Codeforces · 1605/B

B. 反向排序

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

Ashish 有一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,他想要按非递减顺序对其进行排序。

他可以执行以下操作:

1. 选择任意长度的子序列,使其元素按非递增顺序排列。形式上,选择任何 $$$k$$$ 使得 $$$1 \leq k \leq n$$$ 和任何 $$$k$$$ 索引序列 $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$ 使得 $$$s_{i_1} \ge s_{i_2} \ge \ldots \ge s_{i_k}$$$。
2. 就地反转该子序列。正式来说,将 $$$s_{i_1}$$$ 与 $$$s_{i_k}$$$ 交换,将 $$$s_{i_2}$$$ 与 $$$s_{i_{k-1}}$$$、$$$\ldots$$$ 交换,并将 $$$s_{i_{\lfloor k/2 \rfloor}}$$$ 与 $$$s_{i_{\lceil 交换k/2 \rceil + 1}}$$$ (这里$$$\lfloor x \rfloor$$$表示不超过$$$x$$$的最大整数,$$$\lceil x \rceil$$$表示不小于$$$x$$$的最小整数)

查找按非降序对字符串进行排序所需的最少操作数。可以证明,总是可以在最多 $$$n$$$ 操作中对给定的二进制字符串进行排序。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 1000)$$$ — 测试用例的数量。测试用例的描述如下。

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

每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅包含 $$$0$$$s 和 $$$1$$$s。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。

输出

对于每个测试用例输出以下内容:

- 第一行中的最小操作数 $$$m$$$ ($$$0 \le m \le n$$$)。
- 以下 $$$m$$$ 行的格式应为: $$$k$$$ $$$i_1$$$ $$$i_2$$$ ... $$$i_{k}$$$,其中 $$$k$$$ 是长度,$$$i_1 \lt i_2 \lt ... \lt i_{k}$$$ 是所选子序列的索引。对于他们来说,声明中的条件必须成立。

示例

输入 #1

3
7
0011111
5
10100
6
001000

输出 #1

0
1
4 1 3 4 5 
1
3 3 5 6

注意

在第一个测试用例中,二进制字符串已经按非降序排序。

在第二个测试用例中,我们可以执行以下操作:

- $$$k = 4:$$$ 选择索引 $$$\{1, 3, 4, 5\}$$$$$$\underline{1}$$$ $$$0$$$ $$$\underline{1}$$$ $$$\underline{0}$$$ $$$\underline{0}$$$ $$$\rightarrow $$$ $$$\下划线{0}$$$ $$$0$$$ $$$\下划线{0}$$$ $$$\下划线{1}$$$ $$$\下划线{1}$$$

在第三个测试用例中,我们可以执行以下操作:

- $$$k = 3:$$$ 选择索引 $$$\{3, 5, 6\}$$$$$$0$$$ $$$0$$$ $$$\underline{1}$$$ $$$0$$$ $$$\underline{0}$$$ $$$\underline{0}$$$ $$$\rightarrow $$$ $$$0$$$ $$$0$$$ $$$\下划线{0}$$$ $$$0$$$ $$$\下划线{0}$$$ $$$\下划线{1}$$$