hdu 3590——PP and QQ

旧城等待， 2022-07-15 08:58 156阅读 0赞

题意：

有多颗树，然后树上删边游戏，最后一个删的人输。

思路：

其实就是树上删边游戏和anti-sg结合嘛。  
对于树上删边：  
1. 叶子节点的sg为0  
2. 中间节点的sg为所有儿子节点的sg+1的异或和  
对于anti-sg：先手必胜态当且仅当  
1. sg异或值不为0且某个单一游戏的sg>1  
2. sg异或为0且不存在sg>1的单一游戏  
组合起来就好了。

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1e5+5;
    std::vector<int> g[N];
    
    int dfs(int u,int p){
        int ans=0;
        for (int i=0;i<g[u].size();i++){
            int k=g[u][i];
            if (k!=p){
                ans^=(dfs(k,u)+1);
            }
        }
        return ans;
    }
    int main(int argc, char const *argv[])
    {
        int T,n;
        while (~scanf("%d",&T)){
        int ans=0,cnt=0;
        while (T--){
            scanf("%d",&n);
            for (int i=0;i<=n;i++) g[i].clear();
            for (int i=1;i<n;i++){
                int u,v;
                scanf("%d%d",&u,&v);
                g[u].push_back(v);
                g[v].push_back(u);
            }
            int k=dfs(1,-1);
            if (k>1) cnt++;
            ans^=k;
        }
        if ((ans&&cnt)||(!ans&&!cnt)) puts("PP");
        else puts("QQ");
    }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，156人围观）

还没有评论，来说两句吧...

相关阅读

相关 PP-OCR

论文： [PP-OCR: A Practical Ultra Lightweight OCR System][PP-OCR_ A Practical Ultra Lightwe

﹏ヽ暗。殇╰゛Y/ 2022年10月31日 04:13/ 0 赞/ 228 阅读

相关 HDU 5661 Claris and XOR

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5661][http_acm.hdu.edu.cn_showproblem.ph

淩亂°似流年/ 2022年07月28日 10:50/ 0 赞/ 164 阅读

相关 hdu 3590——PP and QQ

题意：有多颗树，然后树上删边游戏，最后一个删的人输。思路：其实就是树上删边游戏和anti-sg结合嘛。对于树上删边： 1. 叶子节点的sg为0 2.

旧城等待，/ 2022年07月15日 08:58/ 0 赞/ 157 阅读

相关 hdu----Lotus and Characters

问题描述 Lotus有$n$种字母，给出每种字母的价值以及每种字母的个数限制，她想构造一个任意长度的串。定义串的价值为：第1位字母的价值1+第2位字母的价值

深碍√TFBOYSˉ_/ 2022年06月15日 01:24/ 0 赞/ 181 阅读

相关 HDU-3595 GG and MM

GG and MM GG and MM like playing a game since the

逃离我推掉我的手/ 2022年06月10日 10:36/ 0 赞/ 122 阅读

相关 HDU 5842-Lweb and String

HDU 5842-Lweb and String -------------------- 题目链接： [Lweb and String][]

超、凢脫俗/ 2022年05月15日 07:04/ 0 赞/ 165 阅读

相关 HDU 6438 Buy and Resell

题目：[点击打开链接][Link 1] 题意：给出 n ，表示 n 天。给出 n 个数，a\[i\] 表示第 i 天，物品的价格是多少。每天可以选择买一个物品，或者卖一

水深无声/ 2022年05月15日 06:58/ 0 赞/ 133 阅读

相关 HDU 1069 Monkey and Banana

原题目链接：[HDU1069][] -------------------- 分类 HDU 动态规划贪心 -------------------- 题意

一时失言乱红尘/ 2022年04月16日 05:53/ 0 赞/ 181 阅读

相关 HDU 1078 FatMouse and Cheese

原题目链接：[HDU1078][] -------------------- 分类 HDU 动态规划 dfs 记忆化搜索 -------------------

一时失言乱红尘/ 2022年04月13日 03:18/ 0 赞/ 176 阅读

相关 HDU 4101 Ali and Baba

长着一张博弈脸的搜索题。给出n\m的地图，有石头空地若干，还有一个宝藏。正整数表示石头的hp，0表示空地，-1表示宝藏，而且保证只有一个。AB轮流敲，每次从边界开始，选一个可达

我不是女神ヾ/ 2022年03月27日 14:26/ 0 赞/ 102 阅读