GG and MM

結論

題意：

每組給n個游戲，每個游戲有兩堆石頭，GG和MM輪流操作，操作規則：

從兩堆里面選出一堆，假設這堆石頭有x個，然后在另一堆里取k*x個石頭(k是正整數)

誰不能取石頭誰輸，MM先手。

思路：

這是一個every——sg游戲。

決定總游戲勝負的是最后一局游戲的勝負。因為不能取石頭的情況就已經是最后一局了，所以之前的游戲勝負情況沒有意義。

那么為了自己能贏，對于自己會贏的游戲，我肯定想盡可能地延長時間，對于自己會輸的游戲，我肯定想盡可能地結束。

那么可以找出每一局所走的時間，最后進行判斷即可。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 1e3 + 10;int a[N], b[N], sg[N][N], step[N][N];int get_sg(int x, int y) {if(x > y) swap(x, y);if(sg[x][y] != -1) return sg[x][y];if(!x || !y) return sg[x][y] = step[x][y] = 0;int tempx = y % x, tempy = x;int k = y / x;if(k == 1) {sg[x][y] = get_sg(tempx, tempy) ^ 1;step[x][y] = step[tempx][tempy] + 1;return sg[x][y];}else {step[x][y] = get_sg(tempx, tempy) + step[tempx][tempy] + 1;return sg[x][y] = 1;} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);memset(sg, -1, sizeof sg);int n;while(scanf("%d", &n) != EOF) {int maxn = 0;for(int i = 1; i <= n; i++) {int x, y;scanf("%d %d", &x, &y);if(x > y) swap(x, y);get_sg(x, y);maxn = max(maxn, step[x][y]);}puts(maxn & 1 ? "MM" : "GG");}return 0; }

總結

以上是生活随笔為你收集整理的GG and MM(every sg 游戏)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。