CF1512C A-B Palindrome 题解
Link
Description
给出 \(T\) 个只由 0、1 和 ? 组成的字符串 \(s\)，将字符串中的 ? 替换成 0 或 1 之后形成一个回文串并且恰好有 \(a\) 个 0 和 \(b\) 个 1，无解输出 -1。
Solution
首先，若不考虑 ? 原串不为回文串一定无解，输出 -1 即可。
下面进行分类讨论。
- 若 \(s_{i}\) 为
?：
- 当 \(s_{n - i + 1}\) 为
0时，\(s_{i}\) 也应该为0，将 \(a\) 减一并将 \(s_{i}\) 改为0。 - 当 \(s_{n - i + 1}\) 为
1时，\(s_{i}\) 也应该为1，将 \(b\) 减一并将 \(s_{i}\) 改为1。 - 当 \(s_{n - i + 1}\) 为
?时，二者相等即可，记录一下个数为 \(cnt\)。
-
若 \(s_{i}\) 为
0：当 \(s_{n - i + 1}\) 为1时，无解。否则 \(a\) 减一即可（对 \(s_{n - i + 1}\) 的处理在枚举到该位置时处理）。 -
若 \(s_{i}\) 为
1：当 \(s_{n - i + 1}\) 为0时，无解。否则 \(b\) 减一即可（对 \(s_{n - i + 1}\) 的处理在枚举到该位置时处理）。
当处理完成时，若 \(a < 0\) 或 \(b < 0\) 或 \(a + b \ne cnt\)无解。
若 \(n\) 为奇数：
-
当 \(s_{\left \lfloor \frac{n}{2} \right \rfloor + 1}\) 为
?时，\(a\) 和 \(b\) 只能有一个为奇数，并将 \(s_{\left \lfloor \frac{n}{2} \right \rfloor + 1}\) 替换为对应的数即可。 -
否则 \(a\) 和 \(b\) 必须均为偶数才有解。
遍历一次，遇到 ? 判断能填哪个就可以了。
Codes
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define max_n 310010
void read(int &p)
{
p = 0;
int k = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
{
k = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9')
{
p = p * 10 + c - '0';
c = getchar();
}
p *= k;
return;
}
void write_(int x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
{
write_(x / 10);
}
putchar(x % 10 + '0');
}
void writesp(int x)
{
write_(x);
putchar(' ');
}
void writeln(int x)
{
write_(x);
putchar('\n');
}
int T;
int a, b, cnt;
char s[max_n];
signed main()
{
#if _clang_
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
read(T);
while (T--)
{
cnt = 0;
read(a), read(b);
scanf("%s", s + 1);
int n = strlen(s + 1);
if (n != a + b)
{
puts("-1");
continue;
}
bool ans = true;
for (int i = 1; i <= n; i++)
{
if (s[i] == '1')
{
if (s[n - i + 1] != s[i] && s[n - i + 1] != '?')
{
ans = false;
break;
}
b--;
}
else if (s[i] == '0')
{
if (s[n - i + 1] != s[i] && s[n - i + 1] != '?')
{
ans = false;
break;
}
a--;
}
else
{
if (s[n - i + 1] == '0')
{
s[i] = '0';
a--;
}
else if (s[n - i + 1] == '1')
{
s[i] = '1';
b--;
}
else
{
++cnt;
}
}
}
if (!ans)
{
puts("-1");
continue;
}
if (a < 0 || b < 0)
{
puts("-1");
continue;
}
else if (cnt == a + b)
{
if (n % 2 == 1 && s[n / 2 + 1] == '?')
{
if ((a & 1) && (!(b & 1)))
{
a--;
s[n / 2 + 1] = '0';
}
else if ((b & 1) && (!(a & 1)))
{
b--;
s[n / 2 + 1] == '1';
}
else
{
puts("-1");
continue;
}
}
else if ((a & 1) || (b & 1))
{
puts("-1");
continue;
}
for (int i = 1; i <= n; i++)
{
if (s[i] == '?')
{
if (a)
{
a -= 2;
s[i] = '0';
s[n - i + 1] = '0';
}
else
{
b -= 2;
s[i] = '1';
s[n - i + 1] = '1';
}
}
putchar(s[i]);
}
puts("");
}
else
{
puts("-1");
continue;
}
}
return 0;
}