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

题解

~~模拟赛的时候竟然场切了，赛后一看是紫。~~

看到这题的第一眼完全没思路，先强行模拟打点暴力分。之后的看看样例手玩一下吧。

首先考虑到向上能是黑色比白色要严格，所以我们考虑如何判断是否是黑色。我们将自己造的数据所有答案为

1

的询问向下在第

0

层对应的矩阵全部打出来，惊奇的发现映入眼帘的是一条全

0

或者全

1

的对角线，随后两边分别跟随了两条颜色与之不同的斜线。于是我们大胆猜测这必然是答案为

1

的充要条件。

具体证明我这里使用递推法，虽然不严谨但主要还是让大家感性理解，并且我的构造过程只包括左上到右下的对角线，另一边同理，

1

表示黑，

0

表示白，

2

表示未处理，

3

表示黑白均可。

第 $0$ 步：

1

第 $1$ 步：由于对角线限制，方案唯一。

10

01

第 $2$ 步：先把上一次操作所有为 $1$ 的处理。

102

010

201

简单推理得到剩下的只能填白色。

100

010

001

第 $3$ 步：依旧先上一次操作所有为 $1$ 的处理。

1022

0102

2010

2201

再把附近的两行

0

处理。

1002

0100

0010

2001

最后我们发现剩下未处理的地方由于剩下了三个白色，所以无论填什么向上都只会保留白色，所以我们不需要处理最外面的

0

。

1003

0100

0010

3001

不难发现，这个优秀的性质能一直维持直到映射到了第

0

层。但是在第

0

层的时候由于题目中相邻立方体不同色的要求，把所有的已经确定的颜色反转不影响结果。

最终，我们得证在题目定义下第

h

层第

i

行第

j

列颜色为黑色当且仅当其对应第

0

层的矩阵内部存在一条全黑或者全白的对角线，对角线向上两条斜线与向下的两条斜线颜色全部与对角线颜色不相同，当

h = 1

时特判即可（结合代码感性理解吧）。

实现时维护两个斜向方向上的对角线的前缀和即可快速判断，时间复杂度

O(N^2+Q)

。

CPP

#include <bits/stdc++.h>
#define maxn 5010
using namespace std;
bool f[maxn][maxn];
int pre1[maxn][maxn];
int pre2[maxn][maxn];
int n, q;
void init(int N, vector<string> M)
{
	n = N;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			f[i][j] = M[i][j] - '0';
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			pre1[i][j] = (j ? pre1[i][j - 1] : 0) + f[(i + j) % n][j], pre2[i][j] = (j ? pre2[i][j - 1] : 0) + f[(i - j + n) % n][j];
}
inline int get1(const int& x, const int& y, const int& h)
{
	int ln = (x - y + n) % n;
	return pre1[ln][y + h] - (y ? pre1[ln][y - 1] : 0);
}
inline int get2(const int& x, const int& y, const int& h)
{
	int ln = (x + y + h) % n;
	return pre2[ln][y + h] - (y ? pre2[ln][y - 1] : 0);
}
bool query(int h, int x, int y)
{
	if (h == 0) return f[x][y];
	if (h == 1) return (f[x][y] && f[x + 1][y + 1] && !f[x + 1][y] && !f[x][y + 1]) || (!f[x][y] && !f[x + 1][y + 1] && f[x + 1][y] && f[x][y + 1]);
	int sum1 = get1(x, y, h), sum2 = get1(x + 1, y, h - 1), sum3 = get1(x, y + 1, h - 1), sum4 = get1(x + 2, y, h - 2), sum5 = get1(x, y + 2, h - 2);
	if (!sum1 && sum2 == h && sum3 == h && sum4 == h - 1 && sum5 == h - 1) return 1;
	if (sum1 == h + 1 && !sum2 && !sum3 && !sum4 && !sum5) return 1;
	sum1 = get2(x, y, h), sum2 = get2(x, y, h - 1), sum3 = get2(x + 1, y + 1, h - 1), sum4 = get2(x, y, h - 2), sum5 = get2(x + 2, y + 2, h - 2);
	if (!sum1 && sum2 == h && sum3 == h && sum4 == h - 1 && sum5 == h - 1) return 1;
	if (sum1 == h + 1 && !sum2 && !sum3 && !sum4 && !sum5) return 1;
	return 0;
}
#ifndef ONLINE_JUDGE
int main()
{
	cin >> n >> q;
	vector<string> s(n);
	for (int i = 0; i < n; i++) cin >> s[i];
	init(n, s);
	static int h, x, y;
	while (q--) cin >> h >> x >> y, cout << query(h, x, y) << '\n';
}
#endif

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

文章操作

题解

相关推荐

评论

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