题解：P10549 [THUPC2024] 简单博弈

Jsxts_ · 2024-06-15 18:18:19 · 题解

非常无聊的题。

看到多个局面同时可操作只有 SG 函数能做。

然后发现因为行与行、列与列之间的地位相同，所以可以任意平移这些行列，将所有的 0 平移到左上后最后本质不同的情况只有 4 种：

000
111
111

001
011
111

001
110
111

011
101
110

考虑之间递推这 4 种情况的 SG 函数。那么由于操作为删掉行列，还会引出下面 4 种情况：

111
111
111

011
111
111

011
101
111

001
111
111

全部递推出来即可。

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e15;
const int N = 500;
inline int read() {
    int s = 0,f = 1;char ch = getchar();
    while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
    while (isdigit(ch)) s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
    return s*f;
}
const int mod = 998244353;
int getmod(int x) {
    return x - (x >= mod) * mod;
}
int qpow(int a,int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % mod;
        b >>= 1, a = 1ll * a * a % mod;
    }
    return res;
}
struct edge {
    int v,nxt;
}ed[N * 2 + 10];
int head[N + 10],cnt;
void add(int u,int v) {
    ed[++cnt] = {v,head[u]};
    head[u] = cnt;
}
int sg[8][N + 10][N + 10],vis[20];
pair<int,int> t[3];
/*
0:
000
111
111
1:
001
011
111
2:
001
110
111
3:
011
101
110
4:
111
111
111
5:
011
111
111
6:
011
101
111
7:
001
111
111
*/
int imp = 19;
int main() {
    for (int i = 1;i <= N;i ++ )
        for (int j = 1;j <= N;j ++ ) {
            vis[sg[4][i - 1][j]] = vis[sg[4][i][j - 1]] = vis[sg[4][i - 1][j - 1]] = 1;
            for (;vis[sg[4][i][j]] == 1;sg[4][i][j] ++ );
            vis[sg[4][i - 1][j]] = vis[sg[4][i][j - 1]] = vis[sg[4][i - 1][j - 1]] = 0;
        }
    for (int i = 1;i <= N;i ++ )
        for (int j = 1;j <= N;j ++ ) {
            vis[sg[5][i - 1][j]] = vis[sg[5][i][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[4][i - 1][j - 1]] = vis[sg[4][i][j - 1]] = vis[sg[4][i - 1][j]] = 1;
            for (;vis[sg[5][i][j]] == 1;sg[5][i][j] ++ );
            vis[sg[5][i - 1][j]] = vis[sg[5][i][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[4][i - 1][j - 1]] = vis[sg[4][i][j - 1]] = vis[sg[4][i - 1][j]] = 0;
            if (i == 1) sg[5][i][j] = sg[4][i][j - 1];
            if (j == 1) sg[5][i][j] = sg[4][i - 1][j];
        }
    for (int i = 1;i <= N;i ++ )
        for (int j = 1;j <= N;j ++ ) {
            vis[sg[6][i - 1][j]] = vis[sg[6][i][j - 1]] = vis[sg[6][i - 1][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[5][i][j - 1]] = vis[sg[5][i - 1][j]] = vis[sg[4][i - 1][j - 1]] = 1;
            for (;vis[sg[6][i][j]] == 1;sg[6][i][j] ++ );
            vis[sg[6][i - 1][j]] = vis[sg[6][i][j - 1]] = vis[sg[6][i - 1][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[5][i][j - 1]] = vis[sg[5][i - 1][j]] = vis[sg[4][i - 1][j - 1]] = 0;
            if (i == 1) sg[6][i][j] = sg[4][i][j - 1];
            if (j == 1) sg[6][i][j] = sg[4][i - 1][j];
        }
    for (int i = 1;i <= N;i ++ )
        for (int j = 1;j <= N;j ++ ) {
            vis[sg[7][i - 1][j]] = vis[sg[7][i][j - 1]] = vis[sg[7][i - 1][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[5][i][j - 1]] = vis[sg[4][i - 1][j - 1]] = vis[sg[4][i - 1][j]] = 1;
            for (;vis[sg[7][i][j]] == 1;sg[7][i][j] ++ );
            vis[sg[7][i - 1][j]] = vis[sg[7][i][j - 1]] = vis[sg[7][i - 1][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[5][i][j - 1]] = vis[sg[4][i - 1][j - 1]] = vis[sg[4][i - 1][j]] = 0;
            if (i == 1) sg[7][i][j] = sg[4][i][max(0,j - 2)];
            if (j <= 2) sg[7][i][j] = sg[4][i - 1][j];
        }
    for (int i = 1;i <= N;i ++ )
        for (int j = 1;j <= N;j ++ ) {
            vis[sg[4][i - 1][j - 1]] = vis[sg[0][i - 1][j - 1]] = vis[sg[7][i - 1][j - 1]] = 1;
            vis[sg[0][i][j - 1]] = vis[sg[7][i][j - 1]] = 1;
            vis[sg[0][i - 1][j]] = vis[sg[4][i - 1][j]] = 1;
            for (;vis[sg[0][i][j]] == 1;sg[0][i][j] ++ );
            vis[sg[4][i - 1][j - 1]] = vis[sg[0][i - 1][j - 1]] = vis[sg[7][i - 1][j - 1]] = 0;
            vis[sg[0][i][j - 1]] = vis[sg[7][i][j - 1]] = 0;
            vis[sg[0][i - 1][j]] = vis[sg[4][i - 1][j]] = 0;
            if (i == 1) sg[0][i][j] = sg[4][i][max(0,j - 3)];
            if (j <= 3) sg[0][i][j] = sg[4][i - 1][j];
        }
    for (int i = 1;i <= N;i ++ )
        for (int j = 1;j <= N;j ++ ) {
            vis[sg[4][i - 1][j - 1]] = vis[sg[1][i - 1][j - 1]] = vis[sg[7][i - 1][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[7][j - 1][i - 1]] = 1;
            vis[sg[1][i][j - 1]] = vis[sg[7][j - 1][i]] = vis[sg[5][i][j - 1]] = 1;
            vis[sg[1][i - 1][j]] = vis[sg[7][i - 1][j]] = vis[sg[5][i - 1][j]] = 1;
            for (;vis[sg[1][i][j]] == 1;sg[1][i][j] ++ );
            vis[sg[4][i - 1][j - 1]] = vis[sg[1][i - 1][j - 1]] = vis[sg[7][i - 1][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[7][j - 1][i - 1]] = 0;
            vis[sg[1][i][j - 1]] = vis[sg[7][j - 1][i]] = vis[sg[5][i][j - 1]] = 0;
            vis[sg[1][i - 1][j]] = vis[sg[7][i - 1][j]] = vis[sg[5][i - 1][j]] = 0;
            if (i <= 2) sg[1][i][j] = sg[5][i][j - 1];
            if (j <= 2) sg[1][i][j] = sg[5][i - 1][j];
        }
    for (int i = 1;i <= N;i ++ )
        for (int j = 1;j <= N;j ++ ) {
            vis[sg[4][i - 1][j - 1]] = vis[sg[2][i - 1][j - 1]] = vis[sg[6][i - 1][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[7][i - 1][j - 1]] = 1;
            vis[sg[7][i][j - 1]] = vis[sg[6][i][j - 1]] = vis[sg[2][i][j - 1]] = 1;
            vis[sg[2][i - 1][j]] = vis[sg[7][i - 1][j]] = vis[sg[5][i - 1][j]] = 1;
            for (;vis[sg[2][i][j]] == 1;sg[2][i][j] ++ );
            vis[sg[4][i - 1][j - 1]] = vis[sg[2][i - 1][j - 1]] = vis[sg[6][i - 1][j - 1]] = vis[sg[5][i - 1][j - 1]] = vis[sg[7][i - 1][j - 1]] = 0;
            vis[sg[7][i][j - 1]] = vis[sg[6][i][j - 1]] = vis[sg[2][i][j - 1]] = 0;
            vis[sg[2][i - 1][j]] = vis[sg[7][i - 1][j]] = vis[sg[5][i - 1][j]] = 0;
            if (i == 1) sg[2][i][j] = sg[4][i][max(j - 2,0)];
            if (j <= 2) sg[2][i][j] = sg[4][i - 1][j];
        }
    for (int i = 1;i <= N;i ++ )
        for (int j = 1;j <= N;j ++ ) {
            vis[sg[5][i - 1][j - 1]] = vis[sg[6][i - 1][j - 1]] = vis[sg[3][i - 1][j - 1]] = 1;
            vis[sg[3][i][j - 1]] = vis[sg[6][i][j - 1]] = 1;
            vis[sg[3][i - 1][j]] = vis[sg[6][i - 1][j]] = 1;
            for (;vis[sg[3][i][j]] == 1;sg[3][i][j] ++ );
            vis[sg[5][i - 1][j - 1]] = vis[sg[6][i - 1][j - 1]] = vis[sg[3][i - 1][j - 1]] = 0;
            vis[sg[3][i][j - 1]] = vis[sg[6][i][j - 1]] = 0;
            vis[sg[3][i - 1][j]] = vis[sg[6][i - 1][j]] = 0;
            if (i < 3 || j < 3) sg[3][i][j] = sg[6][i][j];
        }
    int res = 0;
    int k = read();
    while (k -- ) {
        int n = read(),m = read();
        for (int j = 0;j < 3;j ++ ) t[j].x = read(), t[j].y = read();
        sort(t,t + 3);
        if (t[0].x == t[1].x && t[1].x == t[2].x) res ^= sg[0][n][m];
        else if (t[0].x == t[1].x && (t[2].y == t[0].y || t[2].y == t[1].y)) res ^= sg[1][n][m];
        else if (t[1].x == t[2].x && (t[2].y == t[0].y || t[0].y == t[1].y)) res ^= sg[1][n][m];
        else if (t[0].x == t[1].x && (t[2].y != t[0].y && t[2].y != t[1].y)) res ^= sg[2][n][m];
        else if (t[1].x == t[2].x && (t[2].y != t[0].y && t[0].y != t[1].y)) res ^= sg[2][n][m];
        else if (t[1].x != t[2].x && t[1].x != t[0].x && t[1].y != t[2].y && t[1].y != t[0].y && t[2].y != t[0].y) res ^= sg[3][n][m];
        else {
            sort(t,t + 3,[](pair<int,int> x,pair<int,int> y){return x.y < y.y;});
            if (t[0].y == t[1].y && t[1].y == t[2].y) res ^= sg[0][m][n];
            else if (t[0].y == t[1].y && (t[2].x != t[0].x && t[2].x != t[1].x)) res ^= sg[2][m][n];
            else if (t[1].y == t[2].y && (t[2].x != t[0].x && t[0].x != t[1].x)) res ^= sg[2][m][n];
        }
    }
    puts(res ? "OvO" : "QAQ");
    return 0;
}