HDU - 5996 dingyeye loves stone——阶梯尼姆博弈

HDU - 5996 dingyeye loves stone——阶梯尼姆博弈

题目大意：  dingyeye喜欢和你玩石子游戏。dingyeye有一棵n个节点的有根树，节点编号为0到n−1，根为0号节点。游戏开始时，第i个节点上有a[i]个石子。两位玩家轮流操作，每次操作玩家可以选择一个节点，并将该节点上的一些石子（个数不能为0）移动到它的父亲节点上去。如果轮到某位玩家时，该玩家没有任何合法的操作可以执行，则判负。你在游戏中执先手，你想知道当前局面你能否必胜。

解题思路：

0，将所有深度为奇数的节点的石子数目xor 起来，则先手必胜当且仅当这个 xor和不为 0。 证明同阶梯博弈。对于偶深度的点上的石子，若对手移动它们，则可模仿操作；对于奇深度上的石子，移动一次即进入偶深度的点。 时空复杂度O(n)。

#include #include #include #include #include using namespace std;const int maxn = 1e5 + 10;int n, a[maxn], judge;vector v[maxn];void dfs(int u, int deep) { if (deep & 1) judge ^= a[u]; for (int i = 0; i < v[u].size(); i++) { dfs(v[u][i], deep + 1); }}int main(){ int T; scanf("%d", &T); while (T--) { scanf("%d", &n); judge = 0; for (int i = 0; i <= n; i++) v[i].clear(); for (int i = 1; i < n; i++) { int temp; scanf("%d", &temp); v[temp].push_back(i); } for (int i = 0; i < n; i++) scanf("%d", &a[i]); dfs(0, 0); puts(judge != 0 ? "win" : "lose"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。