Codeforces Round #712 (Div. 2)

A题 Déjà Vu

原题链接

题意:

给定一个字符串, 如果是回文串, 能否通过插入一个\(a\)使其变成非回文串

思路:

先特判一些特殊情况.
对于一般情况, 当\(a_{len - i - 1}\)位置上非\(a\)时, 插入一个\(a\), 完成任务.最后判断是否插入了一个\(a\), 输出结果。

#include 
#include 
#include 

using namespace std;

void solve()
{
    string s;
    cin >> s;
    int l = s.size();
    
    if (l == 1 && s[0] == 'a'){
        cout << "NO" << endl;
        return;
    }

    if (l == 1){
        s += 'a';
        cout << "YES" << endl;
        cout << s << endl;
        return;
    }
    if (l == 2 && s[0] == 'a' && s[1] == 'a'){
        cout << "NO" << endl;
        return;
    }
    if (l == 2 && s[0] == 'a'){
        cout << "YES" << endl;
        cout << "aa";
        cout << s[1] << endl;
        return;
    }
    string ans;
    int flag = 0;
    for (int i = 0; i < l; i ++ ){
        if (s[l - i - 1] != 'a' && flag == 0){
            ans += 'a';
            ans += s[i];
            flag = 1;
        }else{
            ans += s[i];
        }
    }
    if (flag == 0){
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    cout << ans << endl;
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}

B题 Flip the Bits

原题链接

题意：

给定二进制字符串\(a\)和\(b\), 对\(a\), 通过将某一前缀中的\(0 -> 1\)和\(1 -> 0\)操作转化为\(b\), 且要求该前缀中的\(0 1\)个数相同, 问该操作能否实现。

思路:

首先, 当长度为奇数且最后一位\(a、b\)不同时, 一定不能实现.
对于一般情况, 遍历\(a\)：
对于\(a_{i}\), 当前1、0数量分别为\(cnt_{1}\)和\(cnt_{0}\).
当\(cnt_{1} = cnt_{2}\)时, 说明从\(1 - i\)位是可变换的.
另外, 若存在\(00 -> 10 或 11 -> 01\)这些情况时, 则必须在\(1 - i\)位进行转换.
那么, 如果第\(i\)位必须转换但是不可转换, 那么不能实现.

#include 
#include 
#include 

using namespace std;

const int N = 1e5 + 10;

void solve()
{
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    int cnt1 = 0;
    int cnt2 = 0;
    if (n == 1){
        if (a == b)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        return;
    }
    if (n % 2){
        if (a[n - 1] != b[n - 1]){
            cout << "NO" << endl;
            return;
        }
    }
    a[n] = '0';
    b[n] = '0';
    for (int i = 0; i < n; i ++ ){
        if (a[i] == '1')
            cnt1++;
        if (a[i] == '0')
            cnt2++;
        if (((a[i] == a[i + 1]) && (b[i] != b[i + 1])) || (a[i] != a[i + 1] && b[i] == b[i + 1])){
            if (cnt1 != cnt2){
                cout << "NO" << endl;
                return;
            }
        }
    }
    cout << "YES" << endl;
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}

C题 Balance the Bits

原题链接

题意:

给定一个\(01\)字符串, 要求构造两个可以匹配的括号序列, 满足第\(i\)位为\(1\)时, 两个序列相应位置相同, 否则不同.问能否找到满足要求的两个括号序列, 并求出这两个序列.

思路:

首先,判断能否构造这样的括号序列：

1. 首尾必须为\(1\):
   由于括号序列第一位必须为\((\), 最后一位必须为\()\), 即两个序列首尾两个位置必须相同。
2. \(0\)的个数必须为偶数
   假设\(0\)的个数为奇数, 那么\(1\)的个数也为奇数, 当我们成功构造一个括号序列\(a\)后, 对于另一个括号序列\(b\), 由于有奇数个\(1\)(这些位置\(a\)与\(b\)相同), 会产生一个没有配对的括号在\(0\)位置上(即二者必须不同),不能构造出序列\(b\)

判断结束后, 开始构造序列:
所有的\(1\)位置构造出\((\)和\()\),所有\(0\)位置构造出\(a 为 (, )\)序列(b相反)

#include 
#include 

using namespace std;

void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int cnt1 = 0;
    for (int i = 0; i < n; i ++ ){
        if (s[i] == '0')
            cnt1++;
    }
    if (cnt1 % 2){
        cout << "NO" << endl;
        return;
    }
    if (s[0] == '0' || s[n - 1] == '0'){
        cout << "NO" << endl;
        return;
    }
    string a = "(";
    string b = "(";
    int is_1 = 0;
    int is_0 = 0;
    for (int i = 1; i < n - 1; i ++ ){
        if (s[i] == '1'){
            if (is_1){
                a += ')';
                b += ')';
                is_1 = 0;
            }else{
                a += '(';
                b += '(';
                is_1 = 1;
            }
        }else{
            if (is_0){
                a += ')';
                b += '(';
                is_0 = 0;
            }else{
                a += '(';
                b += ')';
                is_0 = 1;
            }
        }
    }
    a += ")";
    b += ")";
    cout << "YES" << endl;
    cout << a << endl
         << b << endl;
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}