C. A-B Palindrome

题意:

给出一串由0,1,?组成的字符串,要求把?变成0或1,保证字符串为回文字符串且满足有a个0,b个1。

题解:

在cf上看到的大佬写的极短的题解(某菜写出来也太长了)。

ACcode:

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int a, b;
        string s;
        cin >> a >> b >> s;
        int len = a + b;
        for (int i = 0; i < len; i++)
            if (s[i] == '?')
            s[i] = s[len - i - 1];
        a -= count(s.begin(), s.end(), '0');
        b -= count(s.begin(), s.end(), '1');//将已经填好的0,1数减去,方便之后填数
        for (int i = 0; i <= len / 2; i++)
        {
            if (i != len - i - 1 && s[i] == '?')
            {
                if (a >1) { s[i] = '0'; s[len - i - 1] = '0'; a -= 2; }
                else if (b >1) { s[i] = '1'; s[len - i - 1] = '1'; b -= 2; }
            }//不是中间字符时,即两边都是?时
            else if(s[i]=='?')
            {
                if (a>0) {
                    s[i] = '0'; a--;
                }
                else if (b > 0)
                {
                    s[i] = '1'; b--;
                }
            }//中间是?时,选不为0的字符填上
        }
        string v = s;
        reverse(v.begin(), v.end());
        if (v == s&&a==0&&b==0)cout << s << endl;
        else cout << "-1" << endl;//判断是否回文
    }
    return 0;
}

(ง •_•)ง

 

上一篇:CodeForces 1335E2 : Three Blocks Palindrome (hard version) 二分 + 思维


下一篇:ural1297 palindrome