C. Ternary XOR

Link

Solution

一道有意思的题，首先明确目的，满足条件的a和b中的较大值尽量小。

从左往右，当s[i]为0时满足条件的a[i]和b[i]只可能是00、12或21，尽量小选00，s[i]为2时同理可得11

问题在于s[i]为1时，首先可以肯定是01或10中的一个（被排除的情况是22），考虑10，当第一个出现分歧（s[i]为0或2时不会出现分歧）的高位a[i]为1且b[i]为0时a和b的最终大小关系其实就已经确定下来了，那么为了满足最终最大值尽量小的条件我们应该怎么做？让较大值（即a）之后位全为0，较小值复制原值即可。

Code

int main() {
    int n, t;
    string s;
    cin >> t;
    while (t--) {
        cin >> n >> s;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0')a[i] = b[i] = 0;
            else if (s[i] == '2')a[i] = b[i] = 1;
            else {
                a[i] = 1, b[i] = 0;
                for (int j = i + 1; j < n; j++)a[j] = 0, b[j] = s[j] - '0';
                break;
            }
        }
        for (int i = 0; i < n; i++)cout << a[i];
        cout << endl;
        for (int i = 0; i < n; i++)cout << b[i];
        cout << endl;
    }
    return 0;
}