6324.Problem F. Grab The Tree

题目看着好难,但是题解说的很简单,写出来也很简单。能想出来就是简单的,想不出来就难(讲道理,就算是1+1的题目,看不出来就是难的啊)。

和后面的东西一点关系都没有。。。

官方题解:

设sum为所有点权的异或和,A为先手得分,B为后手得分。

  • 若sum=0,则A=B,故无论如何都是平局。
  • 否则考虑sum二进制下最高的1所在那位,一定有奇数个点那一位为1。若先手拿走任意一个那一位为1的点,则B该位为0,故先手必胜。

时间复杂度O(n)。

代码:

 //1006-6324-博弈
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
const int maxn=1e5+; int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,ans=;
scanf("%d",&n);
for(int i=;i<=n;i++){
int a;
scanf("%d",&a);
ans^=a;
}
for(int i=;i<n-;i++){
int u,v;
scanf("%d%d",&u,&v);
}
if(ans==) cout<<"D"<<endl;
else cout<<"Q"<<endl;
}
}

嘤嘤嘤,啊啊啊啊啊啊啊啊啊啊啊啊༼༎ຶᴗ༎ຶ༽

05-11 18:39