• 周五. 12月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

暑假集训Day19 K (树上博弈)

admin

11月 28, 2021

题目链接在这里:Problem – K – Codeforces

这题是一道很好的树上博弈的题目,关于博弈论的问题,要先从简单的特殊情况入手,找到一些必胜或者必败的局面,再慢慢推到复杂的情况。因为复杂的状态都是由简单的状态叠加起来的。

关于此题的题解可以看这个博客:(7条消息) MUV LUV UNLIMITED(树上博弈 奇偶性)_jkchen’s Haven-CSDN博客

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=2e6+5;
 4 int t,n;
 5 int tot,head[MAX],adj[MAX],nxt[MAX],son[MAX];
 6 bool flag,ff[MAX];
 7 void addedge(int u,int v){
 8     tot++;
 9     adj[tot]=v;
10     nxt[tot]=head[u];
11     head[u]=tot;
12 }
13 void dfs(int x,int deep){
14     //cout<<x<<endl;
15     int i,j,zt=0;
16     if (x==1){
17         if (son[x]==1) deep++;
18         if ((deep-1)%2==1) flag=false;
19         return;
20     }
21     if (son[x]>1){
22         if ((deep-1)%2==1) flag=false;
23         return;
24     }
25     dfs(adj[head[x]],deep+1);
26 }
27 int main(){
28     freopen ("k.in","r",stdin);
29     freopen ("k.out","w",stdout);
30     int i,j;
31     scanf("%d",&t);
32     while (t--){
33         scanf("%d",&n);tot=0;
34         for (i=1;i<=n;i++) son[i]=head[i]=0;
35         for (i=2;i<=n;i++){
36             scanf("%d",&j);
37             addedge(i,j);
38             //cout<<i<<"-->"<<j<<endl;
39             son[j]++;
40         }
41         flag=true;
42         for (i=1;i<=n;i++)
43             if (son[i]==0)
44                 dfs(i,1);
45         if (flag) printf("Meiya
");
46         else printf("Takeru
");
47     }
48     return 0;
49 }
未来是什么样,未来会发生什么,谁也不知道。
但是我知道,
起码从今天开始努力,
肯定比从明天开始努力,
要快一天实现梦想。
千里之行,始于足下! ——《那年那兔那些事儿》

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注