题目链接
题目意思
小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 ;
}