CF2171C2 Renako Amaori and XOR Game 题解

Mr_RedStone · 2025-12-01 19:08:54 · 题解

思路

设序列 a 的异或和为 s_a，序列 b 的异或和为 s_b。不难发现交换 a_i,b_i 的操作实际上就是：

因此不管经过多少次操作，t=s_a\oplus s_b 永远不变。所以最终造成差别的就是 t 二进制下的最高位的 1。直接找出最后的 i，使得 a_i\oplus b_i 会改变 t 中最高位 1，再判定 i 奇偶性即可。注意特判 s_a=s_b 输出 Tie。

代码

AC 记录

#include<bits/stdc++.h>
using namespace std;
const int NR=2e5+5;
int T,n;
int a[NR],b[NR];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int sa=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sa^=a[i];
        }
        int sb=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            sb^=b[i];
        }
        if(sa==sb){
            printf("Tie\n");
            continue;
        }
        int t=sa^sb;
        int lcz=0;//取出最高位1在哪
        while(t){
            if(t-(t&-t)==0) lcz=__builtin_ffs(t)-1;
            t-=t&-t;
        }
        int lst=0;
        for(int i=1;i<=n;i++){
            if((a[i]^b[i])&(1<<lcz)) lst=i;
        }
        if(lst&1) printf("Ajisai\n");
        else printf("Mai\n");
    }
    return 0;
}