ZOJ 2507 ANTI-SG博弈

本文主要是介绍ZOJ 2507 ANTI-SG博弈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：题目链接

这道题目是一道反nim博弈，求的是谁拿走最后一颗石子输；

分析：

Anti-SG游戏和SJ定理。对于任意一个Anti-SG游戏，如果我们规定当局面中所有的单一游戏的SG值为0时，游戏结束，则先手必胜当且仅当：

（1）游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1；

（2）游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1。

这样，就直接判断就OK；

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
using namespace std;int main()
{int t, n;scanf("%d" ,&t);while(t--){int sum = 0;scanf("%d", &n);int a;int cnt = 0;for(int i = 0; i < n; ++i){scanf("%d", &a);sum ^= a;if(a>1)cnt++;}if(sum){if(cnt)puts("1");elseputs("2");}else{if(cnt)puts("2");elseputs("1");}}return 0;
}

努力努力...

这篇关于ZOJ 2507 ANTI-SG博弈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---