B. 二进制串转回文串

每次测试时间限制：1 秒
内存限制：256 MB

题目描述

给定一个长度为 $n$ 的二进制字符串 $b$。

请构造一个长度为 $n$、由小写英文字母组成的字符串 $s$，使得对于每个 $i$（$1 \le i \le n$），满足：

若 $b_i = 1$，则 $s$ 中所有长度为 $i$ 的子串都是回文串；
若 $b_i = 0$，则 $s$ 中至少有一个长度为 $i$ 的子串不是回文串。

输出满足条件的字典序最小的字符串 $s$。如果不存在这样的字符串，输出 $-1$。

子串定义

字符串 $x$ 是字符串 $y$ 的子串，如果 $x$ 可以通过删除 $y$ 开头若干（可能为零或全部）个字符和结尾若干（可能为零或全部）个字符得到。例如，bc、abc 和 d 都是 abcd 的子串，而 ac 和 ba 不是。

回文串定义

一个字符串是回文串，当且仅当它从左向右读和从右向左读完全相同，即字符串的逆序等于原串。例如，a、aba 和 abba 是回文串，而 ab 和 abc 不是。

字典序定义

字符串 $x$ 比字符串 $y$ 字典序更小，当且仅当：

$x$ 是 $y$ 的真前缀，或
存在某个位置 $i$（$1 \le i \le \min(|x|, |y|)$），使得 $x_i < y_i$，并且对于所有 $j < i$，都有 $x_j = y_j$。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例数。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 3 \times 10^5$）—— 字符串 $b$ 的长度。

第二行包含一个长度为 $n$ 的二进制字符串 $b$，由字符 0 和 1 组成。

保证所有测试用例的 $n$ 之和不超过 $3 \times 10^5$。

输出格式

对于每个测试用例，输出一行：若存在合法字符串，则输出字典序最小的 $s$；否则输出 $-1$。

示例

输入

输出

ab
-1
aaaa

示例说明

第一个测试用例：$b = 10$。长度为 $1$ 的所有子串都必须是回文串（单个字符总是回文），而长度为 $2$ 的唯一子串必须不是回文串。字典序最小的满足条件的字符串是 ab。
第二个测试用例：$b = 001$。由于 $b_1 = 0$，但单个字符总是回文串，因此不存在合法字符串，输出 $-1$。
第三个测试用例：$b = 1111$。所有长度的所有子串都必须是回文串。字典序最小的满足条件的字符串是 aaaa。

思路

这道题很巧妙
我们注意到一个字符，自己一定是回文，一定符合条件
而且如果连续两个字符相同，那么连续两个字符是 $aa$ 第二个和第三个是 $aa$，结果就是连续三个字符也相同，以此类推最后会得到一个全是 $1$ 的情况，对应下列情况1
这道题可以通过分类讨论得出答案

s = $111111$ 任意长度子串都相同，所以最终答案就是 $aaaaaaaa$
s = $101010$ 偶数是 $0$，奇数是 $1$，所以最终答案是 $abababab$
s = $100000$ 所以只有一个字符是符合的，所以答案是 $aaaaaaab$
s = $100001$ 所以一个字符和全选是回文，所以答案是 $aaaaabbaaaaa$ 或者 $aaaaaaabaaaaaa$

代码

//Sunshine sunshine ladybugs awake,
//Clap your hooves and do a little shack.

#include <bits/stdc++.h>
#define int long long
#define endl "\n"

using namespace std;

using PII = pair<int, int>;
const int MAXN = 300005;
const int mod = 998244353;
const int INF = 0x3f3f3f3f3f3f3f3f;

int n;
string s;

// 情况1: b 全为 '1'
bool case1() {
    string type1(n, '1');
    if (s == type1) {
        cout << string(n, 'a') << endl;
        return true;
    }
    return false;
}

// 情况2: b 为 "1010..."（偶数索引为 '1'）
bool case2() {
    string type2(n, '0');
    for (int i = 0; i < n; i++) {
        if (i % 2 == 0) {
            type2[i] = '1';
        }
    }
    if (s == type2) {
        for (int i = 0; i < n; i++) {
            cout << (i % 2 == 0 ? 'a' : 'b');
        }
        cout << endl;
        return true;
    }
    return false;
}

// 情况3: b 为 "100...0"（仅第一个字符为 '1'）
bool case3() {
    string type3 = string(n, '0');
    type3[0] = '1';
    if (s == type3) {
        for (int i = 0; i < n - 1; i++) {
            cout << "a";
        }
        cout << "b" << endl;
        return true;
    }
    return false;
}

// 情况4: b 为 "100...001"（首尾为 '1'，中间全 '0'）
bool case4() {
    string type4(n, '0');
    type4[0] = '1';
    type4[n - 1] = '1';
    if (s == type4) {
        string ans = string(n, 'a');
        // 将中间两个位置改为 'b'，使得整个串不是回文
        ans[(n - 1) / 2] = 'b';
        ans[n / 2] = 'b';
        cout << ans << endl;
        return true;
    }
    return false;
}

void solve() {
    cin >> n >> s;

    if (case1()) return;
    if (case2()) return;
    if (case3()) return;
    if (case4()) return;

    cout << "-1" << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}