题目描述

传送门

样例

#include<iostream>
#include<cstdio>
#define MAXN 50009
using namespace std;
int T, n;
char a[MAXN], b[MAXN];
int main()
{
    cin >> T;
    bool flag = false; // 出现1之前：出现2的都用 1 1
                        // 出现1之后：a[i] = 0, b[i] = 1, 后面的2都用0 2

                        //  
    while(T--){
        cin >> n;
        getchar(); 
        int i = 0;
        flag = false;
        for(i=0; i<n; ++i){
            char tmp = getchar();
            if(tmp == '0'){
                a[i] = '0';
                b[i] = '0';
            } 
            // 没出现1 
            if(!flag){
                if(tmp == '1'){
                    a[i] = '1';
                    b[i] = '0';
                    flag = true; 
                }
                else if(tmp == '2'){
                    a[i] = '1';
                    b[i] = '1';
                } 
            }
            else {
                if(tmp == '1'){
                    a[i] = '0';
                    b[i] = '1';
                }
                else if(tmp == '2'){
                    a[i] = '0';
                    b[i] = '2';
                }
            }
        }
        a[i] = '\0';
        b[i] = '\0';

        getchar(); // 换行符 

        printf("%s\n%s\n", a, b);
    }
}

1. (a+b)%3 = c，相当于a、b的对应的每位加起来%3得到c的该位，即：c[i] = (a[i] + b[i]) %3
2. 要求max(a,b)最小，对于 c[i]=0，必然有 a[i]=b[i]=0
   对于其他情况那么采取以下策略：从前到后逐个遍历c的每位

在出现1之前：
(1) c[i] == 1
令a[i]=0, b[i]=1
(2) c[i] == 2
令a[i]=1, b[i]=1

在出现1之后：
(1) c[i] == 1
令a[i]=0, b[i]=1
(2) c[i] == 2
令a[i]=0, b[i]=2