青山恋弦 2
题目链接:https://codeforces.com/contest/1889/problem/A
题目描述
青山有一串 $s$ ,其中只包含 $\texttt{0}$ 和 $\texttt{1}$ 。
长度为 $k$ 的字符串 $a$ 当且仅当
- 为所有 $i=1,2,\ldots,k$ 的 $a_i \ne a_{k-i+1}$ 。
对于第 2 组的参赛者,请注意这一条件与问题 B 中的条件不同。
例如, $\texttt{10}$ , $\texttt{1010}$ , $\texttt{111000}$ 是好题,而 $\texttt{11}$ , $\texttt{101}$ , $\texttt{001}$ , $\texttt{001100}$ 不是好题。
青山想让 $s$ 变好。为此,她最多可以*** $300$ 次(可能为零)进行以下操作:
- 在 $s$ 的任意位置插入 $\texttt{01}$ (得到一个新的 $s$ )。
请告诉青山,是否有可能使 $s$ 变好。如果可能,请打印出使 $s$ 变好的操作序列。
样例输入
6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001
样例输出
0
-1
-1
2
6 7
1
10
-1
算法1
(暴力枚举)
当字符串a中的1的个数不等于0的个数,无法构造出符合题意的字符串,返回-1
遍历字符串,当两侧都为0,在右侧加上01串;当两侧都为1,在左侧加上01串。
同时对字符串进行处理。
6
001110
0011100011
如果两边都是0 那么在右边+ 01串
4
1001
011001
如果两边都是1 在左边+ 01串
python代码
import sys
input = lambda:sys.stdin.readline().strip()
for _ in range(int(input())):
n = int(input())
a = list(input())
if a.count('0') != n / 2:
print('-1')
continue
ans = []
l, r = 0, n - 1
while l < r:
if a[l] != a[r]:
l += 1
r -= 1
elif a[l] == '0':
a = a[:r + 1] + ['0', '1'] + a[r + 1:]
l += 1
r += 1
ans.append(r)
else:
ans.append(l)
a = a[:l] + ['0','1'] + a[l:]
l += 1
r += 1
print(len(ans))
print(*ans)
算法2
(双端队列)
优化做法:可以用双端队列来维护整个字符串,这样左右插入就会变得很方便,用0,n表示初始插入的位置。
python 代码
import sys
input = lambda:sys.stdin.readline().strip()
from collections import deque
for _ in range(int(input())):
n = int(input())
a = input()
if a.count('0') != n / 2:
print('-1')
continue
q = deque(a)
ans = []
front, rear = 0, n
while q:
if q[0] != q[-1]:
q.pop()
q.popleft()
rear -= 2
elif q[0] == '0':
q.append('0')
q.popleft()
ans.append(rear)
else:
q.appendleft('1')
q.pop()
ans.append(front)
front += 1
rear += 1
print(len(ans))
print(*ans)