锐客网

  1. 首页 > 睿知 > it技术 > >

codeforces 812 E. Sagheer and Apple Tree（树+尼姆博弈）

IT知识codeforces尼姆博弈

黄沙百战穿金甲，不破楼兰终不还。这篇文章主要讲述codeforces 812 E. Sagheer and Apple Tree（树+尼姆博弈）相关的知识，希望能为你提供帮助。
题目链接：http://codeforces.com/contest/812/problem/E
【codeforces 812 E. Sagheer and Apple Tree（树+尼姆博弈）】题意：有一颗苹果树，这个苹果树所有叶子节点的深度要不全是奇数，要不全是偶数，并且包括根在内的所有节点上都有若干个苹果，现有两个，每个人可以吃掉某个叶子节点上的部分苹果（不能不吃），或者将某个非叶子结点上的部分苹果移向它的孩子（当然也不能不移），吃掉树上最后一个苹果的人获胜。后手可以在游戏开始之前交换任意两个不同的节点的苹果，输出交换后能使得后手胜利的交换总数。
 
题解：这题挺友善的所有叶子结点的深度奇偶性是一样的，首先考虑到叶子结点是奇数步的，显然不论先手怎么操作，后手总是能吃掉这些苹果比较显然不解释了。然后就是偶数步时，先手操作一次偶数步时显然偶数步就会变成奇数步，也就是说移动的这部分苹果肯定是先手吃到的。于是就转换到了裸的尼姆博弈，什么是尼姆博弈不知道的可以去百度一下。于是这题只要将所有偶数步的节点上的苹果异或一下如果结果是0那么后手胜利否则先手胜利。
然后就是怎么处理交换了，如果ans=0（ans表示异或结果）那么只要在偶数步与奇数步中交换相同的数即可，还有就是偶数步中与奇数步中分别自行交换。
如果ans！=0那么只要遍历一遍偶数步的点找奇数点中苹果数为ans^val[i]的个数即可。

#include < iostream> #include < string> #include < cstdio> #include < map> #include < vector> using namespace std; typedef long long ll; const int M = 1e5 + 10; map< int , int> num; vector< int> vc[M]; int ans , val[M] , deep[M] , maxdeep; void dfs(int u , int pre , int d) { int len = vc[u].size(); deep[u] = d; maxdeep = max(maxdeep , d); for(int i = 0 ; i < len ; i++) { int v = vc[u][i]; if(v == pre) continue; dfs(v , u , d + 1); } } int main() { int n; scanf("%d" , & n); num.clear(); for(int i = 0 ; i < = n ; i++) vc[i].clear(); for(int i = 1 ; i < = n ; i++) { int gg; scanf("%d" , & gg); val[i] = gg; num[gg]++; } for(int i = 1 ; i < n ; i++) { int gg; scanf("%d" , & gg); vc[gg].push_back(i + 1); vc[i + 1].push_back(gg); } maxdeep = 0; dfs(1 , -1 , 1); for(int i = 1 ; i < = n ; i++) { if((maxdeep % 2) == (deep[i] % 2)) { num[val[i]]-- , ans ^= val[i]; } }//这里处理奇数偶数步用了取巧的方法。就是如果奇偶性和最大深度的奇偶性相同那么就必定是偶数点 ll count = 0; if(ans == 0) { ll sum = 0; for(int i = 1 ; i < = n ; i++) { if((maxdeep % 2) == (deep[i] % 2)) { count += num[val[i]]; } else sum++; } count += (sum * (sum - 1) / 2 + (n - sum) * (n - sum - 1) / 2); } else { for(int i = 1 ; i < = n ; i++) { if((maxdeep % 2) == (deep[i] % 2)) { count += num[(ans ^ val[i])]; } } } printf("%lld\n" , count); return 0; }


    推荐阅读


    上一篇：[LeetCode] 42. Trapping Rain Water

    下一篇：利用Selenium自动化测试android wap页