[C++知识库]C. A-B Palindrome

https://codeforces.com/contest/1512/problem/Care given a string?ss?consisting of the characters '0', '1', and '?'. You need to replace all the characters with '?' in the string?ss?by '0' or '1' so that the string becomes a palindrome and has?exactly?aa?characters '0' and?exactly?bb?characters '1'. Note that each of the characters '?' is replaced?independently?from the others.

A string?tt?of length?nn?is called a palindrome if the equality?t[i]=t[n?i+1]t[i]=t[n?i+1]?is true for all?ii?(1≤i≤n1≤i≤n).

For example, if?s=s="01?????0",?a=4a=4?and?b=4b=4, then you can replace the characters '?' in the following ways:

• "01011010";
• "01100110".

For the given string?ss?and the numbers?aa?and?bb, replace all the characters with '?' in the string?ss?by '0' or '1' so that the string becomes a palindrome and has?exactly?aa?characters '0' and?exactly?bb?characters '1'.

Input

The first line contains a single integer?tt?(1≤t≤1041≤t≤104). Then?tt?test cases follow.

The first line of each test case contains two integers?aa?and?bb?(0≤a,b≤2?1050≤a,b≤2?105,?a+b≥1a+b≥1).

The second line of each test case contains the string?ss?of length?a+ba+b, consisting of the characters '0', '1', and '?'.

It is guaranteed that the sum of the string lengths of?ss?over all test cases does not exceed?2?1052?105.

Output

For each test case, output:

• "-1", if you can't replace all the characters '?' in the string?ss?by '0' or '1' so that the string becomes a palindrome and that it contains?exactly?aa?characters '0' and?exactly?bb?characters '1';
• the string that is obtained as a result of the replacement, otherwise.

If there are several suitable ways to replace characters, you can output any.

Example

input

Copy

9
4 4
01?????0
3 3
??????
1 0
?
2 2
0101
2 2
01?0
0 1
0
0 3
1?1
2 2
?00?
4 3
??010?0

output

Copy

01011010
-1
0
-1
0110
-1
111
1001
0101010

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<deque>
#include<cmath>
#include<string.h>
using namespace std;
// ctrl+shift+C 注释
//ctrl+shift+x 取消
#define int long long
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;
const int N=2e5+10;
const ll M=1e18+10;
const int mod=1e9+7;
int aa[N],sum[N];
priority_queue<int,vector<int>,greater<int> >pq;
set<int>se;
map<char,int>mp;
queue<int>qu;
vector<int>v;
deque<int>de;
int a,b;
string s,ss;
int t=0;
void solve()
{
   cin>>a>>b;
   cin>>s;
   mp.clear();
   int len=s.size();
   for(int i=0;i<len;i++)
   {
       mp[s[i]]++;
   }
   a-=mp['0'];
   b-=mp['1'];
   if(a<0||b<0)
   {
       cout<<-1<<endl;
       return;
   }
   for(int i=0,j=len-1;i<=j;i++,j--)/*必须得先跑一遍循环，优先考虑一个问号和数值的情况*/
   {
     if((s[i]=='1'&&s[j]=='0')||(s[i]=='0'&&s[j]=='1'))//构成不了回文
      {
          cout<<-1<<endl;
          return;
      }
     else if(s[i]!=s[j])
      {
         if(s[i]=='?'&&s[j]=='1')
         s[i]=s[j],b--;
         else if(s[i]=='?'&&s[j]=='0') 
          s[i]=s[j],a--;
         if(s[i]=='1'&&s[j]=='?')
          s[j]=s[i],b--;
         else if(s[i]=='0'&&s[j]=='?') 
         s[j]=s[i],a--;
         if(b<0||a<0)//这时候缺‘0’或者‘1’，明显不能构成回文
         {
             cout<<-1<<endl;
             return;
         }
      }
   }
  for(int i=0,j=len-1;i<=j;i++,j--)//再考虑两个问号的情况
  {
      if((s[i]=='1'&&s[j]=='0')||(s[i]=='0'&&s[j]=='1'))
      {
          cout<<-1<<endl;
          return;
      }
      if(s[i]=='?'&&s[j]=='?'&&i<j)
      {
          
          if(a>=2&&a>=b)//谁多用谁是最优的
          {
              s[i]='0';
              s[j]='0';
             a-=2;
          }
          else if(b>=2&&b>=a)
          {
              s[i]='1';
              s[j]='1';
               b-=2;
          }
          else
          {
              cout<<-1<<endl;
              return;
          }
      }
       else if(s[i]=='?'&&s[j]=='?'&&i==j)
       {
            if(a>0&&a>=b)
          {
              s[i]='0';
              s[j]='0';
              a-=1;
          }
            else if(b>0&&b>=a)
          {
              s[i]='1';
              s[j]='1';
              b-=1;
          }
         else
          {
              cout<<-1<<endl;
              return;
          }
       }
  }
  cout<<s<<endl;
}
signed main()
{
   cin>>t;
  for(int i=1;i<=t;i++)
   {
       solve();
   }
}

思路不难，但是细节多