问题 5757 --兔兔的01串

5757: 兔兔的01串★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 12
[提交][状态][命题人:]

题目描述

给定一个01串s,你可以进行如下操作:
1.选择其中的一个子序列
2.翻转该子序列
请问最少进行多少次上面的操作之后,使字符串有序,即串中所有的0都排在1的前面。

输入

第一行为整数T,表示有T(1≤T≤1000)组测试样例。
每组测试样例的第一行为一个整数n(1≤n≤1000),表示字符串s的长度。
第二个为一个仅有01组成、长度为n的字符串s。
测试数据保证所有n之和为超过1000。

输出

对于每组测试数据按如下格式输出:
 第一行输出最少操作次数m。
 接下来m行格式为: k i1 i2 ... ik(i1<i2<...<ik),其中k为长度(若有多个k值,取最小的k值)。 i1 i2 ... ik为选中序列的位置。
样例输入
Copy
3
7
0011111
5
10100
6
001000
样例输出
Copy
0
1
4 1 3 4 5 
1
2 3 6

提示

第1组测试样例已经是有序的。
第2组测试样例中,选择长度k=4,选择位置为{1,3,4,5}, 1 0 1 0 00 0 0 1 1
第3组测试样例中,选择长度k=2,选择位置为{3,6},   0 0 1 0 0 0 → 0 0 0 0 0 1

来源

 

[提交][状态]