洛谷 P2972：Rocks and Trees G ← 树上Nim博弈

【题目来源】https://www.luogu.com.cn/problem/P2972【题目描述】两个人在一棵有根树上玩 Nim 阶梯游戏。给出一棵有 N 个结点的有根树节点 1 为根每个结点有两个属性 Pi 和 RiPi 表示结点 i 的父亲结点Ri 表示结点 i 的石头数结点 1 没有石头。游戏在两个玩家之间轮流进行Ted 先手。在每一轮这轮的玩家可以选择一个非根结点并且把最多 L 个石头从这个结点向树根靠近一个单位也就是说把这些石头移动到它的父结点处。并且这个玩家至少需要移动一个石子。当某个玩家没有办法移动石子的时候也就是所有的石子都移动到结点 1)游戏结束这个玩家失败。Ted 将会对布局进行 T 次修改。请帮助他确定在每步修改之后以这个布局开局在双方都用最优策略的前提下他是否能赢得这个游戏。Ted 的每次修改由两个数字 x 和 y 描述表示 Ted 将会把结点 x 的石头数修改为 y注意这是一个“设定”操作既不是“减少”也不是“增加”。并且询问修改后谁会获胜。这些修改会累积保持也就是若往后的操作结点 x 的石头数没有修改则结点 x 的石头数会保持在 y个。【输入格式】第 1 行三个空格分隔的整数 N、T 和 L。第 2~N 行每行包含两个空格分隔的整数 Pi 1≤Pii和 Ri1≤Ri≤1000。接下来 T 行每行两个整数 Aj(1Aj≤N) 及 Bj(1≤Bj≤1000)表示 Ted 的每次操作。【输出格式】输出 T 行。如果在第 i 次修改后Ted 可以获胜那么第 i 行输出 Yes否则输出 No。【输入样例】3 2 101 51 32 33 1【输出样例】NoYes【数据范围】2≤N≤10^41≤T≤10^41≤L≤10^3【算法分析】● “洛谷 P2972Rocks and Trees G”整体是树上台阶 Nim即将台阶 Nim 的线性台阶扩展到树形结构深度奇偶替代台阶奇偶每次操作将石子从非根节点移至父节点偶数深度节点可作为“安全缓冲区”被对手模仿抵消因此只有奇数深度节点参与胜负判定。每个奇数深度节点上的石子数记为 cnt受取子上限 L 限制每次只能取 1 到 L 颗这使其单堆退化为巴什博奕SG 值为cnt % (L1)。最终将各奇数深度节点的 SG 值异或若异或和不为零则先手必胜否则先手必败。● SG 值Sprague–Grundy 值 是组合博弈论里用来给公平组合游戏ICG中每一个局面打分的整数核心作用是把五花八门的游戏统一成“和 Nim 一样”的玩法。1每个游戏状态对应一个 SG 值计算方式为考察该状态所有一步可达的后继状态的 SG 值并取该集合的mex 值即不在集合中的最小非负整数作为当前状态的 SG 值显然SG 值一定是非负整数。例如若当前状态所有一步可达的后继状态的 SG 值集合为 {0, 1, 3}则 mex 2若当前状态所有一步可达的后继状态的 SG 值集合为 {0, 1, 2}则 mex 3若没有后继状态即必败态空集合的 mex 0。2SG 值的判定规则为SG 0 表示必败态SG ≠ 0 表示必胜态。多个独立子游戏的总 SG 值为各子游戏 SG 值的异或和由此将任意公平组合游戏纳入 Nim 博弈的统一框架。3不同博弈的 SG 值差异本质上来源于“从当前局面能走到哪些后继局面”的不同规则决定了后继集后继集决定了 mexmex 进而决定了 SG 值。例如在标准 Nim 中单堆石子数为 x时每次可取任意正整数颗1 到 x其后继集包含 0, 1, ..., x-1因此 SG(x) x而在巴什博奕中单堆石子数为 x、每次最多取 L颗时每次只能取 1 到 L颗后继集被限制在 x-L 到 x-1 之间从而 SG(x) x % (L1)。可见取子范围的宽窄直接改变了后继集的构成进而改变了 SG 函数的形态。●巴什博弈Bash Game是一个涉及两名玩家的双人博弈属于公平组合游戏ICG, Impartial Combinatorial Game的典型例子。博弈中有一堆总数为 n 的物品两名玩家轮流从中拿取物品每次至少拿 1 件至多拿 m 件不能不拿最终将物品拿完者获胜。分析如下1n≤m 时由于一次最少拿一个最多拿 m 个甲可以一次拿完先手赢。2nm1 时无论甲拿走多少个 1~m 个剩下的都多于 1 个且少于或等于 m 个乙都能一次拿走剩余的石子后手取胜。上面两种情况可以扩展为以下两种情况。1如果n%(m1)0即 n 是 m1 的整数倍那么不管甲拿多少如 k 个乙都拿 m1-k 个使剩下的永远是 m1 的整数倍直到最后的 m1 个所以后拿的乙一定赢。2如果n%(m1)!0即 n 不是 m1 的整数倍还有余数 r那么甲拿走 r 个剩下的是 m1 的倍数这样就转移到了情况1相当于甲乙互换结果是甲赢。在这个拿石子的游戏中对于后拿的乙来说是很不利的只有在 n%(m1)0 的情况下乙才能赢其他所有情况都是甲赢。●巴什博奕Bash Game是组合博弈中的一类基础游戏特指单堆石子、每次可取 1 到 L 颗、取走最后一颗者胜的独立玩法。【算法代码】#include bits/stdc.h using namespace std; const int N1e45; int fa[N],cnt[N],dep[N]; vectorint g[N]; int n,T,L; int xor_sum; void dfs(int u) { for(int v:g[u]) { dep[v]dep[u]1; dfs(v); if(dep[v]1) xor_sum^(cnt[v]%(L1)); } } int main() { cinnTL; for(int i2; in; i) { cinfa[i]cnt[i]; g[fa[i]].push_back(i); } dfs(1); while(T--) { int pos,val; cinposval; if(dep[pos]1) { xor_sum^(cnt[pos]%(L1)); xor_sum^(val%(L1)); } cnt[pos]val; cout(xor_sum?Yes\n:No\n); } return 0; } /* in: 3 2 10 1 5 1 3 2 3 3 1 out: No Yes */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/158802621https://blog.csdn.net/hnjzsyjyj/article/details/158893015