P14537 [OII 2025] 双色金字塔 / Piramide bicolore

我们每次询问需要求的是，初始矩阵的一个子矩阵

[x, x + h] \times [y, y + h]

作为金字塔的最底层，塔顶的颜色是什么。

手玩

n \le 5

的矩阵很难不发现，塔顶是黑色当且仅当：

对角线是同一种颜色；
不在对角线上且和对角线曼哈顿距离 $\le 2$ 的点都是不同种颜色。

如下：

CPP

100??    011??    ??001    ??110
0100?    1011?    ?0010    ?1101
00100    11011    00100    11011
?0010    ?1101    0100?    1011?
??001    ??110    100??    011??

判断第一种情况，可以令

a_{i, j}

表示是否满足

(i, j), (i + 1, j + 1), (i + 2, j + 2)

都是

1

且

(i, j + 1), (i, j + 2), (i + 1, j), (i + 1, j + 2), (i + 2, j), (i + 2, j + 1)

都是

0

，然后做一个对角线的前缀和。另外三种情况同理。

注意特判

h = 1

。

时间复杂度

O(n^2 + q)

。

代码

CPP

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5050;

int n, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], d[maxn][maxn];
char s[maxn][maxn];

void init(int _n, vector<string> _s) {
	n = _n;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			s[i][j] = _s[i - 1][j - 1];
		}
	}
	for (int i = 1; i <= n - 2; ++i) {
		for (int j = 1; j <= n - 2; ++j) {
			a[i][j] = (s[i][j] == '1' && s[i][j + 1] == '0' && s[i][j + 2] == '0' && s[i + 1][j] == '0' && s[i + 1][j + 1] == '1' && s[i + 1][j + 2] == '0' && s[i + 2][j] == '0' && s[i + 2][j + 1] == '0' && s[i + 2][j + 2] == '1');
			b[i][j] = (s[i][j] == '0' && s[i][j + 1] == '1' && s[i][j + 2] == '1' && s[i + 1][j] == '1' && s[i + 1][j + 1] == '0' && s[i + 1][j + 2] == '1' && s[i + 2][j] == '1' && s[i + 2][j + 1] == '1' && s[i + 2][j + 2] == '0');
		}
		for (int j = 3; j <= n; ++j) {
			c[i][j] = (s[i][j] == '1' && s[i][j - 1] == '0' && s[i][j - 2] == '0' && s[i + 1][j] == '0' && s[i + 1][j - 1] == '1' && s[i + 1][j - 2] == '0' && s[i + 2][j] == '0' && s[i + 2][j - 1] == '0' && s[i + 2][j - 2] == '1');
			d[i][j] = (s[i][j] == '0' && s[i][j - 1] == '1' && s[i][j - 2] == '1' && s[i + 1][j] == '1' && s[i + 1][j - 1] == '0' && s[i + 1][j - 2] == '1' && s[i + 2][j] == '1' && s[i + 2][j - 1] == '1' && s[i + 2][j - 2] == '0');
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			a[i][j] += a[i - 1][j - 1];
			b[i][j] += b[i - 1][j - 1];
		}
		for (int j = n; j; --j) {
			c[i][j] += c[i - 1][j + 1];
			d[i][j] += d[i - 1][j + 1];
		}
	}
}

bool query(int k, int x, int y) {
	++x;
	++y;
	if (k == 1) {
		return s[x][y] == s[x + 1][y + 1] && s[x + 1][y] == s[x][y + 1] && s[x][y] != s[x + 1][y];
	}
	int p = x + k, q = y + k;
	if (a[p - 2][q - 2] - a[x - 1][y - 1] == k - 1) {
		return 1;
	}
	if (b[p - 2][q - 2] - b[x - 1][y - 1] == k - 1) {
		return 1;
	}
	if (c[p - 2][y + 2] - c[x - 1][q + 1] == k - 1) {
		return 1;
	}
	if (d[p - 2][y + 2] - d[x - 1][q + 1] == k - 1) {
		return 1;
	}
	return 0;
}

P14537 [OII 2025] 双色金字塔 / Piramide bicolore

文章操作

相关推荐

评论

P14537 [OII 2025] 双色金字塔 / Piramide bicolore