题目看着好难,但是题解说的很简单,写出来也很简单。能想出来就是简单的,想不出来就难(讲道理,就算是1+1的题目,看不出来就是难的啊)。
和后面的东西一点关系都没有。。。
官方题解:
设sum为所有点权的异或和,A为先手得分,B为后手得分。
- 若sum=0,则A=B,故无论如何都是平局。
- 否则考虑sum二进制下最高的1所在那位,一定有奇数个点那一位为1。若先手拿走任意一个那一位为1的点,则B该位为0,故先手必胜。
时间复杂度O(n)。
代码:
1 //1006-6324-博弈 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<cassert> 8 using namespace std; 9 typedef long long ll; 10 const int maxn=1e5+10; 11 12 int main() 13 { 14 int t; 15 scanf("%d",&t); 16 while(t--){ 17 int n,ans=0; 18 scanf("%d",&n); 19 for(int i=1;i<=n;i++){ 20 int a; 21 scanf("%d",&a); 22 ans^=a; 23 } 24 for(int i=0;i<n-1;i++){ 25 int u,v; 26 scanf("%d%d",&u,&v); 27 } 28 if(ans==0) cout<<"D"<<endl; 29 else cout<<"Q"<<endl; 30 } 31 }
嘤嘤嘤,啊啊啊啊啊啊啊啊啊啊啊啊༼༎ຶᴗ༎ຶ༽