NIMK博弈游戏，POJ-2315 Football Game

淩亂°似流年 2022-06-10 10:07 206阅读 0赞

普通的NIM游戏是在n堆石子中每次选一堆，取任意个石子，而NIMK游戏是在n堆石子中每次选择k堆，1<=k<=n，从这k堆中每堆里都取出任意数目的石子，取的石子数可以不同，其他规则相同。

对于普通的NIM游戏，我们采取的是对每堆的SG值进行异或，异或其实就是对每一个SG值二进制位上的数求和然后模2，比如说3^5就是011+101=112，然后对每一位都模2就变成了110，所以3^5=6。而NIMK游戏和NIM游戏的区别就在于模的不是2，如果是取k堆，就模k+1，所以取1堆的普通NIM游戏是模2。当k=2时，3^5→011+101=112，对每一位都模3之后三位二进制位上对应的数仍然是1，1，2。那么当且仅当每一位二进制位上的数都是0的时候，先手必败，否则先手必胜。

下面是NIMK游戏的模板。

const int MAXN = 10005;
    int SG[MAXN];//需要处理的SG值数组
    int XOR[MAXN];//储存每一个二进制位上的和
    int xxx;//储存每一个SG值的临时变量
    int num;//储存当前SG值有多少位的临时变量
    int maxn;//储存最大的SG值位数
    
    bool solve(int N,int M)//N表示SG数组的大小,从1到N,M表示每次可以取1到M堆
    {
    	memset(XOR, 0, sizeof XOR);
    	maxn = -1;
    	for (int i = 1; i <= N; i++)
    	{
        	xxx = SG[i];
    		num = 0;
    		while (xxx)
    		{
    			XOR[num] += xxx&1;
    			num++;
    			xxx >>= 1;
    		}
    		maxn = max(maxn, num);
    	}
    	for (int i = 0; i < maxn; i++)
    		if (XOR[i] % (M + 1))
    			return true;//返回true表示先手必胜
    	return false;//返回false表示先手必败
    }

POJ-2315就是一道NIMK的标准题目，SG打个表找出规律，然后直接套用模板就行了

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 50;
    const int MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    int SG[MAXN];//需要处理的SG值数组
    int XOR[MAXN];//储存每一个二进制位上的和
    int xxx;//储存每一个SG值的临时变量
    int num;//储存当前SG值有多少位的临时变量
    int maxn;//储存最大的SG值位数
    
    bool solve(int N,int M)//N表示SG数组的大小,从1到N,M表示每次可以取1到M堆
    {
    	memset(XOR, 0, sizeof XOR);
    	maxn = -1;
    	for (int i = 1; i <= N; i++)
    	{
        	xxx = SG[i];
    		num = 0;
    		while (xxx)
    		{
    			XOR[num] += xxx&1;
    			num++;
    			xxx >>= 1;
    		}
    		maxn = max(maxn, num);
    	}
    	for (int i = 0; i < maxn; i++)
    		if (XOR[i] % (M + 1))
    			return true;//返回true表示先手必胜
    	return false;//返回false表示先手必败
    }
    
    int N, M, L, R;
    int s;
    
    int main()
    {
    	while (scanf("%d%d%d%d", &N, &M, &L, &R) != EOF)
    	{
    		s = L / (2 * PI*R);
    		for (int i = 1; i <= N; i++)
    		{
    			scanf("%d", &SG[i]);
    			SG[i] = SG[i] / (2 * PI*R) + 1;
    			SG[i] %= s + 1;//打表找出的SG值的规律
    		}
    		if (solve(N, M))
    			printf("Alice\n");
    		else
    			printf("Bob\n");
    	}
    }