Codeforces Round 1065 (Div. 3)

A. Shizuku Hoshikawa and Farm Legs

void solve(){
    int n;
    cin >> n;
    if(n % 2){
        cout << 0 << endl;
        return ;
    }

    int cnt = 0;
    for(int i = 0; i <= n / 2; ++i){
        if((n - 2 * i) % 4 == 0) cnt++;
    }
    cout << cnt << endl;
    return ;
}

B. Yuu Koito and Minimum Absolute Sum

题目要求 min(|b1+b2+⋯+bn−1|) , bi=ai+1−ai，这不就是差分吗。最小化 |b1+b2+⋯+bn−1| 的和，经过差分化简 |a1 - an| 的最小值，那么只要 a1 与 an 相同就能得到最小值为0，那我么只需要考虑数组 a 的第一个元素和最后一个元素就行了。题目中还要求输出从字形上看最小的数组，根据解释， 让中间为 -1 的变成 0 就行了。

总之就是考虑第一个元素和最后一个元素就行了，中间为 -1 的元素用 0 代替，分类讨论就行。

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    if(a[1] == -1 || a[n] == -1){
        cout << 0 << endl;
    }else{
        cout << abs(a[n] - a[1]) << endl;
    }

    if(a[1] == -1 && a[n] == -1){
        for(int i = 1; i <= n; ++i){
            if(a[i] == -1) cout << 0 << " ";
            else cout << a[i] << " ";
        }
    }else if(a[1] == -1 || a[n] == -1){
        if(a[1] == -1){
            cout << a[n] << " ";
            for(int i = 2; i <= n; ++i){
                if(a[i] == -1) cout << 0 << " ";
                else cout << a[i] << " ";
            }
        }else{
            for(int i = 1; i < n; ++i){
                if(a[i] == -1) cout << 0 << endl;
                else cout << a[i] << " ";
            }
            cout << a[1] << " ";
        }
    }else{
        for(int i = 1; i <= n; ++i){
            if(a[i] == -1) cout << 0 << " ";
            else cout << a[i] << " ";
        }
    }
    cout << endl;
    return ;
}

C1. Renako Amaori and XOR Game (easy version)

博弈论问题，奇数轮 Ajisai 操作，偶数轮 Mai 操作，两个人在各自回合都尽可能得让自己的分数比对方多。如果 2n 个数每个数都是 ai = bi 那么两个人的异或和相同， 如果 ai != bi 的数量为偶数， 那么两人的异或和也是相等的，这两种情况都会达到平局 “Tie”。那么在 ai != bi 的数量为奇数的情况下，能让自己的分数比对方高的情况通过分析应该是最后一次  ai != bi 时的位置，这是因为该简单版本两人的成绩只有 0 或 1，若想改变两边的大小， 只有当 ai != bi 时才能改变，也就是说最后一次 ai != bi 时的位置决定了两人的胜负，若 i 为奇数时，Ajisai 胜， 否则 Mai 胜。

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];

    int cnt1 = 0, cnt2 = 0, cnt = 0;
    int t1 = 0, t2 = 0;
    stack<int> st;
    for(int i = 1; i <= n; ++i){
        if(a[i] != b[i]){
            if(i % 2 == 1) t1++;
            else t2++;
            st.push(i);
        }
    }

    if(t1 % 2 == t2 % 2){
        cout << "Tie" << endl;
    }else{
        if(st.top() % 2 == 1){
            cout << "Ajisai" << endl;
        }else{
            cout << "Mai" << endl;
        }
    }
    return ;
}

C2. Renako Amaori and XOR Game (hard version)

对于困难版本，如果对方想赢，那么异或和最高位的 1 位置应该比 另一方要大。通过枚举每一位二进制，题目中 ai 的大小 < 1e6, 那么二进制位最大取20就足够了。从高到低枚举 先统计 最高位 为j时的个数，只有当数量为奇数时，最高位才存在，紧接着从后到前枚举，依旧是跟简单版本的思路一样，最后的数决定成败，而这里是到什么位置能够取到最高位j。

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    int k = 0;
    for(int i = 1; i <= n; ++i) k ^= a[i] ^ b[i];
    // if(!k){
    //     cout << "Tie" << endl;
    //     return ;
    // }

    for(int j = 20; j >= 0; --j){
        int cnt = 0;
        for(int i = n; i >= 1; --i){
            int u = a[i] >> j & 1;
            int v = b[i] >> j & 1;
            if(u ^ v) cnt++;
        }

        if(cnt % 2){
            for(int i = n; i >= 1; --i){
                if((a[i] ^ b[i]) >> j & 1){
                    if(i % 2){
                        cout << "Ajisai" << endl;
                    }else{
                        cout << "Mai" << endl;
                    }
                    return ;
                }
            }
        }
    }
    cout << "Tie" << endl;
    return ;
}

D. Rae Taylor and Trees (easy version)

对于序列中的任意两个数值 a 和 b，如果 a < b，则 a 和 b 是可连通的（要么直接有边，要么能通过中间数值间接连通）。我们认为，如果每两个节点都能连通，那么就能构成一张无向图。

先计算每个节点的前缀最小值 pre 和 后缀最大值 suf， 若想 pi-1 和 pi 相连。应该prei-1 < sufi ，为什么呢？

对于prei-1，可知，prei-1<=pi-1，对于sufi，可知 pi <= sufi，也就是说在 1~i-1 的范围里，一定存在一个节点或者 pi-1 自身的节点相连，在 i~n的范围内，一定也存在一个数与pi相连或者pi自身，并且 1~i-1的一个节点与 i~n的一个节点也必定相连，这样就实现了pi-1和pi之间的相连。 

通过遍历每个数，只要所有数都满足此要求输出 “Yes”,否则 “No”.

void solve(){
    int n;
    cin >> n;
    vector<int> p(n + 1);
    for(int i = 1; i <= n; ++i) cin >> p[i];
    vector<int> suf(n + 2, 0), pre(n + 1, 0);
    for(int i = n; i >= 1; --i){
        if(p[i] > suf[i + 1]){
            suf[i] = p[i];
        }else{
            suf[i] = suf[i + 1];
        }
    }

    pre[0] = 2e5 + 5;
    for(int i = 1; i <= n; ++i){
        if(p[i] < pre[i - 1]){
            pre[i] = p[i];
        }else{
            pre[i] = pre[i - 1];
        }
    }
    
    for(int i = 2; i <= n; ++i){
        if(pre[i - 1] > suf[i]){
            cout << "No\n";
            return ;
        }
    }
    cout << "Yes\n";
    return ;
}