A-B Palindrome

Love The Way You Lie 2024-05-01 16:05 44阅读 0赞

给你一个只包含字符 '0', '1', 和 '?' 的字符串 ss。你需要用 '0' 或 '1' 替换 ss 中的所有 '?' 从而使得 ss 变成一个回文串并且 正好有 aa 个 '0' 以及 正好有 bb 个 '1'. 注意每个字符 '?' 都是 独立于 其他字符被替换.

如果一个长度为 nn 的字符串 tt 对于所有的 i(1\\le i\\le n)i(1≤i≤n) 都满足 t\[i\]=t\[n-i+1\]t\[i\]=t\[n−i+1\] 那么 tt 被称为回文串

例如，如果 s=s="01?????0", a=4a=4 并且 b=4b=4, 那么你可以用以下方法替换 '?' :

*  "01011010";
 *  "01100110".

对于给定的字符串 ss 以及整数 aa 和 bb, 用 '0' 或 '1' 替换 ss 中所有的 '?' 从而使的字符串 ss 回文 并且 正好有 aa 个 '0' 以及 正好有 bb 个 '1'.

Input

> 第一行一个整数 tt (1 \\le t \\le 10^41≤t≤104). 下面是 tt 个测试样例.
> 
> 每个测试样例第一行有两个整数 aa 和 bb (0 \\le a, b \\le 2 \\cdot 10^50≤a,b≤2⋅105, a + b \\ge 1a+b≥1).
> 
> 每个测试样例第二行是一个长度为 a+ba+b 的字符串 ss, 包含字符 '0', '1', 和 '?'.
> 
> 保证所有测试样例字符串 ss 的长度和不超过 2 \\cdot 10^52⋅105.

Output

> 对每个测试样例输出:
> 
>  *  "-1", 如果你无法对于给定的字符串 ss 以及整数 aa 和 bb, 用 '0' 或 '1' 替换 ss 中所有的 '?' 从而使的字符串 ss 回文 并且 正好有 aa 个 '0' 以及 正好有 bb 个 '1';
>  *  否则输出你替换所有的 '?' 且满足条件的字符串
> 
> 如果有多个正确的构造方式，输出任意一个即可.

Example

Input

>     9
>     4 5
>     ?1???0110
>     1 1
>     ??
>     0 1
>     ?
>     2 2
>     0101
>     2 2
>     01?0
>     0 1
>     0
>     3 0
>     0?0
>     2 2
>     1??1
>     2 5
>     ??010??

Output

>     011010110
>     -1
>     1
>     -1
>     0110
>     -1
>     000
>     1001
>     1101011

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    int main()
    {
        int t,i,a,b;
        scanf("%d",&t);
        while(t--)
        {    int a1=0,b1=0,c1=0,find=0,n;
             char s[400005];
             scanf("%d%d",&a,&b);getchar();
             scanf("%s",s);
             for(i=0;i<=a+b-1;i++)
             {
                 if(s[i]=='1')b1++;
                 if(s[i]=='0')a1++;
                 if(s[i]=='?')c1++;
             }
             n=a+b;
             for(i=0;i<=a+b-1;i++)//回文对称数相同
             {
                 if(s[i]=='1'&&s[n-i-1]=='?')
                     s[n-i-1]='1',b1++;
                 if(s[i]=='0'&&s[n-i-1]=='?')
                     s[n-i-1]='0',a1++;
             }
             for(i=0;i<n;i++)
             {
                 if(s[i]!=s[n-1-i])
    				{find=1;break;}
    			if(i==n-i-1&&s[i]=='?')//如果总数奇数中间一位为？
                {
                    if(a1<=a-1)
                        s[i]='0',a1++;
                    else if(b1<=b-1)
                        s[i]='1',b1++;
                }
                if(s[i]=='?'&&s[n-i-1]=='?')//如果对称两项为？
                {
                    if(a1<=a-2)
                       s[i]=s[n-i-1]='0',a1+=2;
                    else if(b1<=b-2)
                       s[i]=s[n-i-1]='1',b1+=2;
                }
             }
             if(a1==a&&b1==b&&find==0)  puts(s);
                else  printf("-1\n");
        }
        return 0;
    }