題目連結
題目意思
小Q和小T要玩一個遊戲,現在有一顆節點數為N的樹,每個節點有一個權值。現在小Q可以選擇任意不相鄰的節點,小Q選完以後剩餘的所有節點都歸小T。現在小Q和小T的分數就是所選的所有節點的權異或和,誰的分數高誰就赢了,如果分數相同就是平局。誰赢輸出誰,平局輸出D。
解題思路
根據異或的性質Q異或T會等于全部異或和。是以Q隻要取異或總和最高為為1的那部分。剩下肯定比他小。但如果全部異或為0那麼兩人就相同了。
代碼部分
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=+;
int main()
{
int t;
int n,s,u,v,a;
scanf("%d",&t);
while(t--)
{
s=;
scanf("%d",&n);
for(int i=; i<n; i++)
{
scanf("%d",&a);
s^=a;
}
for(int i=; i<n-; i++)
{
scanf("%d%d",&u,&v);
}
if(s==)
printf("D\n");
else
printf("Q\n");
}
return ;
}