CF1512C A-B Palindrome 题解

题目大意

给定一个字符串（长度为 $a+b$），给定 $a$，$b$。

$a$ 表示字符串里有几个 $0$，$b$ 表示字符串里有几个 $1$。

并且要求字符串回文。

让你把字符串中的 $?$ 替换成 $0$ 或 $1$。

关于解法

首先判断原字符串是否合法。

然后暴力枚举每一个元素，如果是 $?$ 就给填上。

中间位置要特判！

代码

#include<bits/stdc++.h>
using namespace std;
#define I return
#define AK 0
#define IOI ;
int t,a,b,f;
string s;
int main()
{
	cin>>t;
	while(t--)
	{
		cin>>a>>b>>s,f=0;
		if(a%2==1 && b%2==1)
		{
			cout<<-1<<endl;
			continue;
		}
		for(int i=0;i<s.size();i++)
		{
			if(s[s.size()-i-1]!=s[i] && s[i]!='?' && s[s.size()-i-1]!='?')//不满足回文 
			{
				f=1;
				break;
			}
			if(s[i]!='?' && s[s.size()-i-1]=='?') s[s.size()-i-1]=s[i];//如果一方已知就补全回文
		}
		for(int i=0;i<s.size();i++) a-=s[i]=='0',b-=s[i]=='1';//判断到底是a减还是b减，懒得用if
		if(a<0 || b<0 || f)//f在这里一起判断，可以压行 
		{
			cout<<-1<<endl;
			continue;
		}
		for(int i=0;i<s.size() && !f;i++)
		{
			if(s[i]!='?') continue;//s[i]有值就不用管
			if(i==s.size()/2)//在中间 
			{
				if(a%2==1)
				{
					s[i]='0',a--;
					continue;
				}
				if(b%2==1)
				{
					s[i]='1',b--;
					continue;
				}
				f=1;
			}
			if(f) continue;
			if(a>=2)
			{
				s[i]=s[s.size()-i-1]='0',a-=2;
				continue;
			}
			if(b>=2)
			{
				s[i]=s[s.size()-i-1]='1',b-=2;
				continue;
			}
			f=1;
		}
		if(f)
		{
			cout<<-1<<endl;
			continue;
		}else cout<<s<<endl;
	}
	I AK IOI
}