1 条题解

  • 0
    @ 2025-8-24 22:59:05

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Jsxts_
    [憨笑]

    搬运于2025-08-24 22:59:05，当前版本为作者最后更新于2024-06-15 18:18:19，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    非常无聊的题。

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

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

    000
111
111

001
011
111

001
110
111

011
101
110

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

    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;
}
    • 1

    [THUPC 2024 决赛] 简单博弈

    信息

    ID
    10307
    时间
    2000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 21ms