HDU 5963(游戏博弈+规律)

题意是：

一群男生和一群女生玩游戏：给出一棵 n 个节点的树，这棵树的每条边有一个权值 0 或 1。在一局游戏开始时，确定一个节点作为根。从女生开始，双方轮流进行操作。

当一方操作时，要先选择一个不为根且到其父亲的边权为 1 的点，然后找出这个点到根节点的简单路径，将路径上所有边的权值翻转（即 0 变成 1，1 变成 0 )。

当一方无法操作时（即所有边的边权均为 0），另一方就获得了胜利。双方均采用最优策略，若女生获胜，则输出 “Girls win!”，否则输出“Boys win!”。

每局之间可能会有修改边权的操作，且每局游戏指定的根节点也可能是不同的。

开始时以为会很麻烦，借鉴了别人的博客，才想到修改边权只能每次修改一条边的，有了一些思路：

首先要明确结果只有两种，当操作数为奇数时女生获胜，当操作数为偶数时男生获胜。

一、这种情况下需要经过两次操作才能将所有权值置 0 ；二、这种情况下需要经过一次或三次操作才能将所有权值置 0 ；

三、这种情况下需要经过两次或四次操作才能将所有权值置 0 ；四、这种情况下需要经过三次或五次操作才能将所有权值置 0。

上述四种情况的结论是只要进行操作就一定会出现的，不一定要特别采用最优策略，也就是说情况出现后先手与后手的输赢已经确定，双方只要按规则操作即使想可以改变结果也

无法做到，其实应该还有第五种情况，就是都为 0 的情况，这种情况下需要零次操作才能将所有权值置 0。

发现，当与根结点相连的边权和为偶数时需要且一定经过偶数次操作才能将所有权值置 0，当与根结点相连的边权和为奇数时需要且一定经过奇数次操作才能将所有权值置 0。

开始时打算用 40000*40000 的 bool 数组去存，但还是超内存了……

错误代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 bool p[40010][40010];
 4 int main()
 5 {
 6     int t,n,m,x,y,z;
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         scanf("%d%d",&n,&m);
11         memset(p,0,sizeof(p));
12         for(int i = 1; i < n; ++i)
13         {
14             scanf("%d%d%d",&x,&y,&z);
15             p[x][y] = z;
16             p[y][x] = z;
17         }
18         for(int i = 0; i < m; ++i)
19         {
20             scanf("%d",&z);
21             if(z)
22             {
23                 scanf("%d%d%d",&x,&y,&z);
24                 p[x][y] = z;
25                 p[y][x] = z;
26             }
27             else
28             {
29                 scanf("%d",&z);
30                 x = 0;
31                 for(int i = 0; i < 40000; ++i)
32                     if(p[z][i]) ++x;
33                 if(x&1) puts("Girls win!");
34                 else puts("Boys win!");
35             }
36         }
37     }
38     return 0;
39 }

View Code

改成 vector 数组才过了

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 vector<int> p[40010];
 4 int num[40010];
 5 int main()
 6 {
 7     int t,x,y,z,n,m;
 8     scanf("%d",&t);
 9     while(t--)
10     {
11         scanf("%d%d",&n,&m);
12         memset(num,0,sizeof(num));
13         memset(p,0,sizeof(p));
14         for(int i = 1; i < n; ++i)
15         {
16             scanf("%d%d%d",&x,&y,&z);
17             if(z)
18             {
19                 ++num[x];
20                 ++num[y];
21                 p[x].push_back(y);
22                 p[y].push_back(x);
23             }
24         }
25         for(int i = 0; i < m; ++i)
26         {
27             scanf("%d",&z);
28             if(z)
29             {
30                 scanf("%d%d%d",&x,&y,&z);
31                 vector<int>::iterator it1 = find(p[x].begin(),p[x].end(),y);
32                 vector<int>::iterator it2 = find(p[y].begin(),p[y].end(),x);
33                 if(it1!=p[x].end() && z==0)
34                 {
35                     --num[x];
36                     --num[y];
37                     p[x].erase(it1);
38                     p[y].erase(it2);
39                 }
40                 if(it1==p[x].end() && z==1)
41                 {
42                     ++num[x];
43                     ++num[y];
44                     p[x].push_back(y);
45                     p[y].push_back(x);
46                 }
47             }
48             else
49             {
50                 scanf("%d",&z);
51                 if(num[z]&1) puts("Girls win!");
52                 else puts("Boys win!");
53             }
54         }
55     }
56     return 0;
57 }

View Code

感谢这篇博客的作者：

https://blog.csdn.net/song_4/article/details/53063309

HDU 5963(游戏 博弈+规律)

HDU 5963(游戏博弈+规律)