HDU 3032 multi-sg 打表找规律

普通NIM规则加上一条可以分解为两堆,标准的Multi-SG游戏

一般Multi-SG就是根据拓扑图计算SG函数,这题打表后还能发现规律

sg(1)=1

sg(2)=2

sg(3)=mex{0,1,2,1^2}=4

sg(4)=mex{0,1,2,sg(3)}=3

可以发现3和4的时候相当于互换了位置

/** @Date    : 2017-10-12 21:20:21
* @FileName: HDU 3032 博弈 SG函数找规律.cpp
* @Platform: Windows
* @Author : Lweleth (SoungEarlf@gmail.com)
* @Link : https://github.com/
* @Version : $Id$
*/
#include <bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std; const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8; int main()
{
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
int ans = 0;
for(int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
if(x % 4 == 3)
ans ^= x + 1;
else if(x % 4 == 0)
ans ^= x - 1;
else ans ^= x;
}
if(ans) printf("Alice\n");
else printf("Bob\n");
}
return 0;
}
//SG(1)=1
//SG(2)=2
//SG(3)=MEX{1,2,1^2}
//SG(4)=MEX{1,2,SG(3)} //互换先后手
上一篇:多线程---静态同步函数的锁是class(转载)


下一篇:Docker: 限制容器可用的 CPU