首页 > 代码库 > hdu5795 A Simple Nim 求nim求法,打表找sg值规律 给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空) 或者选择一堆,把它分成三堆,每堆不为空。求先手必胜,还是后手必胜。
hdu5795 A Simple Nim 求nim求法,打表找sg值规律 给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空) 或者选择一堆,把它分成三堆,每堆不为空。求先手必胜,还是后手必胜。
/** 题目:A Simple Nim 链接:http://acm.hdu.edu.cn/showproblem.php?pid=5795 题意:给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空) 或者选择一堆,把它分成三堆,每堆不为空。求先手必胜,还是后手必胜。 思路: 组合游戏Nim; 计算出每一堆的sg值,然后取异或。异或和>0那么先手,否则后手。 对于每一堆的sg值求解方法: 设:sg(x)表示x个石子的sg值。sg(x) = mex{sg(x-1),sg(x-2),...,sg(0),sg(a)^sg(b)^sg(c) |(a+b+c==x)} 当sg(0) = 0; sg(1) = 1; sg(2) = 2; sg(x>=3)就要通过上面式子算出来了。 通过打表可以发现规律。 当x>=3.如果x是8的倍数,那么sg=x-1. 如果(x+1)是8的倍数,那么sg=x+1. */ #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> P; const int maxn = 1e6+10; const int mod = 1e9+7; int T, n; int main() { cin>>T; while(T--) { scanf("%d",&n); int ans = 0; for(int i = 0; i < n; i++){ int x; scanf("%d",&x); if(x%8==0&&x!=0){ ans ^= x-1; }else { if((x+1)%8==0){ ans ^= x+1; }else { ans ^= x; } } } printf("%s\n",ans?"First player wins.":"Second player wins."); } return 0; }
hdu5795 A Simple Nim 求nim求法,打表找sg值规律 给定n堆石子,每堆有若干石子,两个人轮流操作,每次操作可以选择任意一堆取走任意个石子(不可以为空) 或者选择一堆,把它分成三堆,每堆不为空。求先手必胜,还是后手必胜。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。