A - Two Lucky Numbers

题目大意： 给出两个数A，B，找到一个数中同时包含A，且乘2后包含B。

比如13 62，符合的就是131，因为131包含13和 131 \times 2 = 262包含62。

题解:

挺好想的，首先A可以直接打印出来因为这个数中就直接包含A

然后在考虑二倍里包含B， 既然二倍包含B，我们可以直接让B /2 就可以得到原来的值，但是如果B是奇数，显然直接/2的值是不对的。

所以可以先乘一个10，然后再除二，就可以构造出符合题意的数了。

最后，还要考虑如果B是个位数的问题，因为进位的1可能会和A的个位数相加。所以如果B是个位数，则在AB间加一个0来分隔开即可。

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    printf("%d", a);
    if(b / 2 < 1){
        printf("0");
    }
    printf("%d", b * 10 / 2);
}

B - Grid Repainting 4

题目大意:

给一个H * W的矩阵，其中有一些空填了1-5的数字，有些空为'.'，要求你任意填入1-5使得每个数字的上下左右没有相同的数字。

数据范围:1 <= H,W <= 700

题解:

因为一个格子附近只有上下左右四个数，所以对于每一个格子来说一定会有一个数可以填入。

数据范围很小，直接选择遍历判断，选一个能填入的填进去就行了。

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

char f[800][800];
char op[] = {'1','2','3','4','5'};
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

int main(){
    int h,w;
    cin>>h>>w;
    for(int i = 1; i <= h; i++){
        char xxx; scanf("%c", &xxx);
        for(int j = 1; j <= w; j++){
            scanf("%c", &f[i][j]);
        }
    }
    for(int i = 0; i < 5; i++){
        for(int j = 1; j <= h; j++){
            for(int k = 1; k <= w; k++){
                if(f[j][k] == '.'){
                    int flag = 1;
                    for(int l = 0; l < 4; l++){
                        int u = j + dx[l];
                        int v = k + dy[l];
                        if(u < 1 || u > h || v < 1 || v > w) continue;
                        if(f[u][v] == op[i]){
                            flag = 0;
                            break;
                        }
                    }
                    if(flag) f[j][k] = op[i];
                }
            }
        }
    }
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            printf("%c", f[i][j]);
        }
        printf("\n");
    }
}

C - Zero XOR

题目大意:

有N个不重复的数，你和另一个人每一次都可以从这些数中取出一个数，如果剩下的数XOR和为0，那么最后一个取的人获胜。现在给出N个数问谁一定能获胜。（博弈论）

题解:

这题真的好难= =博弈论太难想了

首先上结论:

如果N是奇数，那么先手的人一定会赢。

如果N是偶数，如果N当中有一个数等于将N个数全部XOR后的值，那么先手赢，否则后手赢。

接下来是证明：

我们定义u为先手的玩家，v为后手的玩家。

对于奇数的情况来说，我们假设u输了，那么必然是在u取了一个数之后，v取一个数，然后剩下的数的XOR和为0。那么，同样的如果u取了v取的数，v也可以取u取的数，让剩下的数XOR和为0。因此存在着一对数，使得只要u取了其中一个，v都可以取另一个让游戏获胜。 但是此时的桌子上有奇数个数，那么就意味着一定有一个数是无法组成这种对子的。只要u拿了这个数，v就没有办法终结游戏(因为没有和这个数配对的，可以让剩下XOR和为0的数)。

这样一来只要u不断找出这个落单的数，就可以将游戏不断继续下去，直到数被取完，即u获胜。

而对于偶数，如果u无法在第一步终结游戏，那么u和v的角色将会转换，变为奇数的情况，所以如果没有一个数可以让u获胜，那么v就会赢。

那么为什么找到一个数等于所有数的XOR和就可以判定u能在第一步终结游戏呢？

因为:

v\ =\ A_1\ XOR \ A_2 \ XOR ⋯\ XOR\ A_N

而 0 \ XOR \ N = \ N

所以就意味着有N-1个数的的XOR和为0，才能让他 XOR v后还是v

代码(AtCoder 官方题解):

#include <iostream>
using namespace std;
int N, A[400009];
int v = 0;
int main() {
    // Step #1. Input
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];

    // Step #2. Compute A[1] xor A[2] xor ... xor A[N]
    for (int i = 1; i <= N; i++) v ^= A[i];
    // Step #3. Branching and output
    if (N % 2 == 1) {
        cout << "Win" << endl;
    }
    else {
        bool winning = false;
        for (int i = 1; i <= N; i++) {
            if (A[i] == v) winning = true;
        }
        if (winning == true) cout << "Win" << endl;
        else cout << "Lose" << endl;
    }
    return 0;
}

同时，Atcoder还提供了一种暴力(相对)的解法，但是我觉得也挺难想的，大概就是每层递归都转变先手的玩家去判断。

#include <iostream>
#include <vector>
using namespace std;
// returns true if the first player wins with the cookies vec[0], vec[1], ..., vec[vec.size()-1]
bool solve(vector<int> vec) {
    // if XOR is 0, the second player wins
    int All_XOR = 0;
    for (int i = 0; i < vec.size(); i++) {
        All_XOR ^= vec[i];
    }
    if (All_XOR == 0) {
        return false;
    }
    // otherwise...
    for (int i = 0; i < vec.size(); i++) {
        // take the i-th cookie
        vector<int> nex;
        for (int j = 0; j < vec.size(); j++) {
            if (j != i) nex.push_back(vec[j]);
        }
        bool ret = solve(nex);
        if (ret == false) return true; // first player wins
    }
    return false; // second player wins
}
int main() {
    // input
    int N; cin >> N;
    vector<int> A(N, 0);
    for (int i = 0; i < N; i++) cin >> A[i];
    // output
    bool Answer = solve(A);
    if (Answer == true) cout << "Win" << endl;
    else cout << "Lose" << endl;
    return 0;
}