题解：P17405 【MX-X31-T1】「FAOI-R14」四元博弈

Remember_longlong · 2026-09-05 18:38:05 · 题解

题目传送门

思路

诈骗题，诈骗我。

结论：

假设 a_1=0 时先手必败，那么 a_1\neq0 时，先手选择 x=1,t=a_1，把必败局面给后手。所以后手必败，先手必胜。

现在证明为什么 a_1=0 时，先手必败。

显然此时先手不能选择 x=1，因为 a_1\oplus y=y\ge a_1。那么先手只能操作 x\neq1,y>0。操作之后，a_1 会变成 y（a_1'=y），那么后手就可以选择 x=1,y=a_1'，于是 a_1 又会变成 0。由于游戏必然在有限步结束，最终轮到先手时无法操作，先手必败。 ::::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N=25;
int t,n,a[N];
signed main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",a+i);
        for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v);
        if(a[1]!=0) printf("Si\n");
        else printf("Yuan\n");
    }
    return 0;
}

::::