admin 管理员组

文章数量: 887007

hdu 5963:朋友

刚看到这题时感觉是树上博弈，然后我开始用一维的数据找规律。发现在一维的树上，如果把各边的值合在一起当成一个二进制数，那么，ans只与奇偶性有关，于是，我提出了一个比较大胆的假设：若连接在root上的所有边异或和为1，则girls win，否则boys win。然后强力大腿队友立马就把我这想法用代码实现了，在oj上一交，没过，我想，算了，也许是想法错了，打算再想想，突然队友发现#define N 400000 里，N小了，改大一点点再交，卧槽！这特么居然真的可以AC！后来看别人博客，发现了一个不错的理解这个原理的思路，就是，只考虑与跟相邻的边，每次男生或者女生进行操作时，根的一条临边都必然取反，而最终状态是各临边全为0，显然，这个总操作数的奇偶性为必然的，与各临边异或和有关。下面有我今天自己刚刚补上的代码。

题目链接： .php?pid=5963

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int ans[400005];
 5 
 6 map< pair<int,int>,int> edges;
 7 
 8 int main()
 9 {
10     int T;
11     scanf("%d",&T);
12     while(T--)
13     {
14         int n,m,x,y,z,op;
15         scanf("%d%d",&n,&m);
16         memset(ans,0,sizeof(ans));
17         edges.clear();
18         for(int i=1;i<n;i++)
19         {
20             scanf("%d%d%d",&x,&y,&z);
21             if(x>y) swap(x,y);
22             edges[make_pair(x,y)]=z;
23             ans[x]^=z;
24             ans[y]^=z;
25         }
26         while(m--)
27         {
28             scanf("%d",&op);
29             if(op)
30             {
31                 scanf("%d%d%d",&x,&y,&z);
32                 if(x>y) swap(x,y);
33                 if(edges[make_pair(x,y)]!=z)
34                 {
35                     ans[x]^=1;
36                     ans[y]^=1;
37                 }
38                 edges[make_pair(x,y)]=z;
39             }
40             else
41             {
42                 scanf("%d",&x);
43                 printf("%s\n",ans[x]?"Girls win!":"Boys win!");
44             }
45         }
46     }
47 }

 

转载于:.html

本文标签： hdu 5963朋友

版权声明：本文标题：hdu 5963:朋友 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732355844h1534412.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。