Xor 思维题

题目描述

(Q)与小(T)正在玩一棵树。这棵树有(n)节点,编号为 (1)(2) (3…n),由(n-1)条边连接,每个节点有一个权值(w_i)

在这个游戏中,小 (Q) 需要选择一些节点。他可以选择任意个数的点(小(Q)一定会选择最优策略),但是一条边连接的两个节点不能同时被选。

当小(Q)选完后,小(T)将选择剩下的节点。这样这棵树上的每个点都将被小(Q)或者小(T)选择。

最后两人的分数分别为自己选择的点的权值异或和,分数大的一方获胜,当然有可能是平局。

输入格式

第一行一个整数(T(T leq 20)),表示测试数据组数

接下来(T)组,对于每一组,第一行一个整数(n)

第二行有(n)个整数,为(w_1,w_2…w_n)

接下来(n-1)行,每行两个整数(x)(y),表示(x)(y)

之间有一条边连接

输出格式

对于每一组,答案只有一行,如果小(Q)获胜输出(Q),小(T)获胜输出(T),如果平局输出(D)

样例

样例输入

2
3
2 2 2
1 2
1 3
4
7 1 4 2
1 2
1 3
2 4

样例输出

Q
D

样例解释

在第一组中,小(Q)选择任意一个节点,分数为(2),小(T)选择剩下两个节点,分数为(0),小(Q)获胜

在第二组中,小(Q)最好只能和小(T)平局,所以输出(D)
数据范围与提示

对于$30% (的数据,)n leq 20$
对于(100%)的数据,(n leq 100000),(w_i leq 10^9)

分析

一道不错的思维题

首先我们考虑平局的情况

如果整棵树上所有节点的异或和恰好为(0)的话

那么无论先手选走哪一些点,后手选走的点一定与先手选走的点相同,这样才能保证异或和为(0)

如果整棵树上所有节点的异或和不为(0),那么我们在二进制位中会找到一个最高位的(1)

先手只要把这个(1)选走,那么必定可以获胜

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],n;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int tot=0;
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            tot^=a[i];
        }
        for(int i=1;i<n;i++){
            int aa,bb;
            scanf("%d%d",&aa,&bb);
        }
        if(tot==0) printf("Dn");
        else printf("Qn");
    }
    return 0;
}

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» Xor 思维题

发表评论

免登录下载网,提供全网最优质的资源集合!