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

· · 题解

题解

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

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

首先考虑到向上能是黑色比白色要严格，所以我们考虑如何判断是否是黑色。我们将自己造的数据所有答案为 1 的询问向下在第 0 层对应的矩阵全部打出来，惊奇的发现映入眼帘的是一条全 0 或者全 1 的对角线，随后两边分别跟随了两条颜色与之不同的斜线。于是我们大胆猜测这必然是答案为 1 的充要条件。

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

1 $01 $010$\ $201

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

$010$\ $001 $0102$\ $2010$\ $2201

再把附近的两行 0 处理。

$0100$\ $0010$\ $2001

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

$0100$\ $0010$\ $3001

不难发现，这个优秀的性质能一直维持直到映射到了第 0 层。但是在第 0 层的时候由于题目中相邻立方体不同色的要求，把所有的已经确定的颜色反转不影响结果。

最终，我们得证在题目定义下第 h 层第 i 行第 j 列颜色为黑色当且仅当其对应第 0 层的矩阵内部存在一条全黑或者全白的对角线，对角线向上两条斜线与向下的两条斜线颜色全部与对角线颜色不相同，当 h = 1 时特判即可（结合代码感性理解吧）。

实现时维护两个斜向方向上的对角线的前缀和即可快速判断，时间复杂度 O(N^2+Q)。

#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