Acwing 893：集合Nim游戏（博弈论 sg函数）

心已赠人 2022-09-14 09:19 137阅读 0赞

#### 题目链接 ####

传送门：[Acwing 893：集合Nim游戏][Acwing 893_Nim]

#### 题目大意 ####

先给定一个集合s，有k个元素。然后有n堆石子，每堆分别有 h i h\_i hi个，每次都可以从某一堆中取出x个石子（这里的x规定必须是集合s中的一个元素），两个人轮流取最优，问是否先手必胜。（ 1 ≤ n , k ≤ 100 1≤n,k≤100 1≤n,k≤100， 1 ≤ s i , h i ≤ 10000 1≤s\_i,h\_i≤10000 1≤si,hi≤10000）

--------------------

#### 大致思路 ####

这就是一个变形的[Nim博弈][Nim]，我们每次取的个数不是任意的了，而是在规定的集合s中选一个数，取这么多个石子。因此我们就用[sg函数][Nim]来求解，求出每堆石子的sg，然后将所有的sg异或起来，是0的话先手必败，否则先手必胜。

--------------------

#### 代码模板 ####

#include<iostream>
    #include<cstring>
    #include<unordered_set>
    using namespace std;
    const int N = 10010;
    
    int k,n,h,ans,s[N],f[N];
    
    int sg(int x)			//求sg函数，实际就是一个记忆化搜索
    { 
    	if(f[x] != -1)		//如果f[x]已经求过了，直接返回
    		return f[x];
    	unordered_set<int> S;	//用一个集合S来去重，S装x所有能到达的状态
    	for(int i = 0;i < k;i++)//循环这k个数
    		if(x >= s[i])		//如果x大于等于s[i]，说明能取s[i]个
    			S.insert(sg(x-s[i]));	//将取走s[i]后的状态装入集合S
    	for(int i = 0; ;i++)	//从0开始枚举所有的自然数
    		if(!S.count(i))		//如果自然数i不存在与集合S中
    			return f[x] = i;	//i就是其的mex值，返回i，并存于f[x]中
    }
    
    int main()
    { 
    	memset(f,-1,sizeof f);
    	cin >> k;		//集合s的大小为k
    	for(int i = 0;i < k;i++)	//k个数，每次只能取这k个数中的一个
    		cin >> s[i];
    	cin >> n;		//n堆石子
    	for(int i = 0;i < n;i++)
    	{ 
    		cin >> h;
    		ans ^= sg(h);	//将每堆石子的sg异或起来
    	}	 
    	if(ans)			//如果不是0，先手必胜
    		cout << "Yes" << endl;
    	else			//如果是0，先手必败
    		cout << "No" << endl;
    	
    	return 0;
    }

[Acwing 893_Nim]: https://www.acwing.com/problem/content/895/
[Nim]: https://blog.csdn.net/qq_45735851/article/details/108285065