A. Domino Disaster

• meaning of the title
  Here you are 2 × n 2 \times n two × The grid of n is now used 1 × 2 1\times 2 one × 2's dominoes fill the grid. The state of the domino in the first row is given. You need to construct the legal state of the second line.

• Problem solving ideas
  If placed horizontally, the first and second rows complement each other. If it is placed vertically, the state of the second row should be opposite to that of the first row, that is, one up and one down. Therefore, if it is placed horizontally, we will repeat the placement state of the first line, otherwise we can place it in the opposite state.

• AC code

/**
  *@filename:A_Domino_Disaster
  *@author: pursuit
  *@created: 2021-09-05 22:36
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t, n;
char s[N];
void solve(){
    char pre = ' ';
    for(int i = 1; i <= n; ++ i){
        if(s[i] == 'U'){
            printf("D");
        }
        else if(s[i] == 'D'){
            printf("U");
        }
        else{
            printf("%c", s[i]);
        }
    }
    puts("");
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d%s", &n, s + 1);
        solve();
    }
    return 0;
}

B. MEXor Mixup

• meaning of the title
  Here you are a , b a,b a,b. You need to construct the shortest sequence so that M E X = a , X O R = b MEX=a,XOR=b MEX=a,XOR=b. M E X MEX MEX represents the smallest non negative integer that does not appear in the sequence, X O R XOR XOR represents the exclusive or sum of all elements in the sequence.

• Problem solving ideas
  According to the requirements of the topic, we want to make M E X = a MEX=a MEX=a, then < a <a All elements of < a must be in the sequence, so the sequence length is at least l e n len len, at the same time, we need to ask for difference or sum. If we ask for difference or sum directly, it will inevitably timeout. Therefore, we need to use XOR prefix and preprocessing to get 3 e 5 3e5 The data of 3e5, of course, can also be obtained by properties 0 0 0~ n n The XOR sum of n can be based on n n n right 4 4 Determination of remainder of 4:

  • If the remainder is 0 0 0, XOR and n n n；
  • If the remainder is 1 1 1, then XOR and 1 1 1；
  • If the remainder is 2 2 2, then XOR and n + 1 n +1 n+1；
  • If the remainder is 3 3 3, then XOR and 0 0 0.

  This nature is not proved. You can refer to relevant information, push it by hand or write it down.
  After dealing with this, we get the XOR and as r e s res res, if r e s = b res = b res=b, then we don't need to add elements. What if they are not equal? We need to add at least one element to make the XOR and b b b. Suppose the added value is x x x. So x = r e s x= res x=res^ b b b.
  We need special judgment at this time x x x. Because if x = a x=a x=a we can't take it. At this time, we need to select two elements to get XOR a a a. at this time, there are only two elements to be added.
  So far, the problem is solved.

• AC code

/**
  *@filename:B_MEXor_Mixup
  *@author: pursuit
  *@created: 2021-09-05 22:39
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t, a, b;
void solve(){
    int res, len = a;
    int x = a - 1;
    if(x % 4 == 1)res = 1;
    else if(x % 4 == 2)res = a;
    else if(x % 4 == 3)res = 0;
    else res = x;
    if(res == b){
        cout << len << endl;
        return;
    }
    int temp = (res ^ b);
    if(temp == a){
        //Description cannot be selected.
        cout << len + 2 << endl;
    }
    else{
        cout << len + 1 << endl;
    }
}
int main(){	
    cin >> t;
    while(t -- ){
        cin >> a >> b;
        solve();
    }
    return 0;
}

C. Carrying Conundrum

• meaning of the title
  Define an additive carry, two forward bits, and give a sum n n n. Ask how many positive integer combinations (a,b) are there so that sum is n n n.

• Problem solving ideas
  There are many methods for this problem, such as DFS and DP, which consider whether to carry or not.
  The simplest method is introduced here. We note that each carry is carried by the first two bits. In other words, adjacent numbers do not affect each other, that is, those with different parity positions do not affect each other. Therefore, we can consider it separately according to parity:
  For example, for 12345 12345 12345, we can split it according to parity 135 135 135 and 24 24 24, then the number formed by their separation is the normal addition, and the previous carry. In this case, the number of schemes is n u m + 1 num +1 num+1, so we can get the total number of schemes is ( a n s 1 + 1 ) × ( a n s 2 + 1 ) (ans1+1)\times (ans2+1) (ans1+1) × (ans2+1), but it is not over yet. Note that it is a positive integer combination, and the number of schemes is the number of schemes in all cases, then it also includes ( 0 , n ) , ( n , 0 ) (0,n),(n,0) (0,n),(n,0) these two schemes are inconsistent, so the final answer is ( a n s 1 + 1 ) × ( a n s 2 + 1 ) − 2 (ans1+ 1)\times(ans2+1)-2 (ans1+1)×(ans2+1)−2.

• AC code

/**
  *@filename:C_Carrying_Conundrum
  *@author: pursuit
  *@created: 2021-09-05 22:57
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t, n, a[12], len;
ll res;
void solve(){
    len = 0;
    int temp = n;
    while(temp){
        a[++ len] = temp % 10;
        temp /= 10;
    }
    ll ans1 = 0, ans2 = 0;
    for(int i = len; i >= 1; -- i){
        if(i & 1){
            ans2 = ans2 * 10 + a[i];
        }
        else{
            ans1 = ans1 * 10 + a[i];
        }
    }
    cout << (ans1 + 1) * (ans2 + 1) - 2 << endl;
}
int main(){	
    cin >> t;
    while(t -- ){
        cin >> n;
        solve();
    }
    return 0;
}

D. Expression Evaluation Error

• meaning of the title
  Number of given positive integers n n n. Given at the same time 10 10 Sum in decimal s s s. You need to construct n n n numbers so that they use 11 11 The sum and maximum formed by binary calculation.

• Problem solving ideas
  Because we use 10 10 Hexadecimal, but in 11 11 Binary calculation, so for 19 19 19. The value we converted into is 1 × 1 1 1 + 9 × 1 1 0 1\times 11^1+9\times 11^0 one × 111+9 × 110. We note that if we can construct high-order 10 10 To the power of 10, the higher the sum (because the cardinality is 11 11 11). So at first we can s s s press 10 10 To the tenth power.
  Then consider the number that can be expressed s u m sum sum, you need to pay attention here, s u m ≥ n sum\geq n sum ≥ n does not affect because 10 + 10 = 20 10+10=20 10 + 10 = 20, as long as there is no carry, it is feasible. The key is s u m < n sum<n Sum < n, we need to make up, then destroy 10 10 To the 10th power, we must start to destroy from the low position, assuming that i i The value of bit i minus 1 1 1, then the second i − 1 i-1 i − 1 bit can be added up 10 10 Ten, so we have more 9 9 9 numbers. Note that it is necessary to greedily start to gather from the low position until the low position cannot be gathered, and then turn to the high position.
  After processing, s u m ≥ n sum\geq n sum≥n. At this time, we need to consider merging to make it into n n n. The merging needs to start from the high position. Pay attention to the details.

• AC code

/**
  *@filename:D_Expression_Evaluation_Error
  *@author: pursuit
  *@created: 2021-09-06 00:09
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

//D. dismantle 10 ^ P directly without brain. The larger the P, the better
int t, n, s;
int power[11];
void init(){
    power[0] = 1;
    for(int i = 1; i <= 9; ++ i){
        power[i] = power[i - 1] * 10;
    }
}
void solve(){
    vector<int> a;
    int sum = 0;
    while(s){
        a.push_back(s % 10);
        sum += s % 10;//sum is expressed as the number of the largest 10th power that can be rounded up.
        s /= 10;
    }
    while(sum < n){
        //We need to get together at this time. From low to high.
        for(int i = 1; i < a.size(); ++ i){
            if(a[i] > 0){
                -- a[i], a[i - 1] += 10;
                sum += 9;
                break;//sign out. That is, I want to use the low bit. If you can't get to the top, you can't get to the top.
            }
        }
    }
    vector<int> res;
    for(int i = a.size() - 1; i >= 0; -- i){
        for(int j = 0; j < a[i]; ++ j){
            res.push_back(power[i]);
        }
    }
    while(res.size() > n){
        int x = res.back();
        res.pop_back();
        res.back() += x;
    }
    for(int i = 0; i < res.size(); ++ i){
        cout << res[i] << " ";
    }
    cout << endl;
}
int main(){	
    init();
    cin >> t;
    while(t -- ){
        cin >> s >> n;
        solve();
    }
    return 0;
}