CFCF2192B.Flipping Binary String
普及-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
给定一个长度为 n 的二进制字符串 s。你可以对字符串进行如下操作:
- 选择一个下标 i,并翻转除了第 i 位以外所有位置上的比特。也就是说,选择一个整数 i(1≤i≤n),对于所有 j 满足 1≤j≤n 且 j=i,如果 sj=0,则将 sj 置为 1;否则将 sj 置为 0。
你可以对字符串进行任意次数的上述操作,但每个下标最多只能被选择一次。
你的任务是通过若干次操作,把字符串 s 的所有比特都变为 0,或者判断这不可能做到。你不需要最小化操作次数。
输入格式
每个测试包含若干组测试数据。第一行包含测试组数 t(1≤t≤104)。接下来是每组测试数据的描述。
每组测试数据的第一行包含一个整数 n(1≤n≤2×105)。
第二行是一个长度为 n 的二进制字符串 s。
保证所有测试数据中 n 的总和不超过 2×105。
输出格式
对于每组测试数据,如果无法将所有比特变成 0,输出 −1。否则,输出两行:
- 第一行,输出操作次数 x(0≤x≤n)。
- 第二行,输出 x 个数,表示依次选择进行操作的下标。每个下标最多只能选择一次。
如果存在多组可行解,你可以输出任意一种。
输入输出样例
输入#1
4 3 101 3 100 4 0000 4 1010
输出#1
1 2 -1 0 2 1 3
说明/提示
在第一个样例中,对第 2 位进行操作,相当于翻转第 1 位和第 3 位的比特。操作后,字符串变为 000。
在第二个样例中,可以证明无法通过上述操作将字符串 a 变为 000。