ZOJ 2083 SG博弈

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

题目：题目链接

题目意思：题目是说两个人给n条线染色，每次可以染的长度是2.A先手，问A是赢还是输？假设双方都采取最好的策略

分析：思路：裸求SG函数，和把一排石子分成若干堆相似，每次把长度为x的线段分成长度为i和x-i-2的线段，然后异或后求出mex值（mex值指不属于这个集合的非负整数），最后把所有子游戏的SG值异或求和

代码：

#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 n;
int sg[55];
int SG(int m)
{if(m < 2)return sg[m] = 0;if(sg[m] != -1)return sg[m];bool next[55];memset(next, 0, sizeof(next));for(int i = m-2; i >= 0; --i){int tp = SG(i)^SG(m-i-2);next[tp] = 1;}for(int i = 0;; ++i){if(next[i]==0)return sg[m] =  i;}
}
int main()
{memset(sg, -1, sizeof(sg));while(scanf("%d", &n)==1){int sum = 0;int a;for(int i = 0; i < n; ++i){scanf("%d",&a);sum ^= SG(a);}if(sum)puts("Yes");else puts("No");}return 0;
}

努力努力...

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

---