阿里巴巴国际站跨境电商平台,免费查公司信息,网络规划与设计论文开题报告,网站建设需要哪些人员1002.Random Nim Game
诈骗博弈题
题目大意
Nim是一种双人数学策略游戏#xff0c;玩家轮流从不同的堆中移除棋子。在每一轮游戏中#xff0c;玩家必须至少取出一个棋子#xff0c;并且可以取出任意数量的棋子#xff0c;条件是这些棋子都来自同一个棋子堆。走最后一步棋…1002.Random Nim Game
诈骗博弈题
题目大意
Nim是一种双人数学策略游戏玩家轮流从不同的堆中移除棋子。在每一轮游戏中玩家必须至少取出一个棋子并且可以取出任意数量的棋子条件是这些棋子都来自同一个棋子堆。走最后一步棋即取出最后一块棋子的人获胜。
现在更改游戏规则在每个回合中棋手必须选择一个棋子堆。假设他选择的堆包含 x x x 个棋子将从 [ 1 , x ] [1,x] [1,x] 中随机一个整数 y y y 并从堆中移除 y y y 个棋子
求先手获胜的概率答案取模
解题思路
看起来很吓人的一道题谁被吓退了我不说//
考虑只有一个堆的情况 若只有 1 1 1 个棋子先手必胜 如果有 2 2 2 个棋子有 1 2 \dfrac{1}{2} 21 的概率拿完获胜有 1 2 \dfrac{1}{2} 21 的概率余 1 1 1 失败综合胜率 1 2 \dfrac{1}{2} 21 ⋮ \vdots ⋮ 如果有 x ( x 1 ) x\ (x1) x (x1) 个棋子有 n − 2 n \dfrac{n-2}{n} nn−2 的概率转移到 剩余个数 1 1 1 的状态有 1 n \dfrac{1}{n} n1 的概率拿完获胜有 1 n \dfrac{1}{n} n1 的概率余 1 1 1 失败。递归得到 x 1 x1 x1 的状态下的综合胜率为 1 2 \dfrac{1}{2} 21
再考虑多堆的情况 如果所有堆的棋子数量均为 1 1 1 则当堆数 n n n 为奇数时先手必胜 如果有某堆的数量多于 1 1 1 个那么必胜态将以 1 2 \dfrac{1}{2} 21 的概率流转
综上所述如果所有堆的棋子数量均为 1 1 1 则当堆数 n n n 为奇数时先手必胜 n n n 为偶数时先手必败其余情况综合胜率 1 2 \dfrac{1}{2} 21
参考代码 参考代码为已AC代码主干其中部分功能需读者自行实现 void solve()
{ll n;cin n;ll mx0,t;FORLL(i,1,n){cin t;mxmax(mx,t);}if(mx1) cout inv(2) endl;else if(n%2) cout 1 endl;else cout 0 endl;
}
