问题 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为选中序列的位置。
提示
第1组测试样例已经是有序的。
第2组测试样例中,选择长度k=4,选择位置为{1,3,4,5}, 1 0 1 0 0 → 0 0 0 1 1
第3组测试样例中,选择长度k=2,选择位置为{3,6}, 0 0 1 0 0 0 → 0 0 0 0 0 1
来源
[提交][状态]