NIMK博弈游戏，POJ-2315 Football Game

2019-04-14 11:58发布

站内文章 / 模拟电子
13742 0 1203
普通的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 #include #include #include #include #include #include #include #include #include #include #include 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 "); else printf("Bob "); } }

热门文章