「yww 与魔法阵」题解

题目大意

给定一个 $n$ 行的三角形矩阵，每行 $i$ 有 $i$ 个元素。元素值为 $0$ 表示水晶完好，$1$ 表示水晶损坏。需要找到最大的正三角形区域（不能有缺口，中间是空的），使得该区域内所有水晶都是完好的（值为 $0$）。输出这个最大三角形的面积（即包含的水晶数量）。

解题思路

关键观察

1. 三角形结构：矩阵呈三角形排列，第 $i$ 行有 $i$ 个元素
2. 正三角形约束：只能选择正着放的等腰直角三角形
3. 预处理信息：需要快速判断某个三角形区域是否全为 $0$

算法核心

预处理数组

1. lft[i][j]：记录第 $i$ 行第 $j$ 个位置向左第一个损坏水晶的位置
2. dwn[i][j]：记录第 $i$ 行第 $j$ 个位置向下第一个损坏水晶的位置

主算法流程

对于每个可能的三角形大小，检查是否存在满足条件的三角形区域：

1. 按对角线扫描：对于每条对角线（从左上到右下），找到连续的完好水晶段
2. 滑动窗口检查：使用单调栈维护可能的三角形候选
3. 二分优化：通过二分查找确定最大的可行三角形大小

代码解析

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

// 快速读入
int read() {
    char ch = '!';
    int res = 0, f = 0;
    while (!isdigit(ch)) {
        ch = getchar();
        if (ch == '-') f = 1;
    }
    while (isdigit(ch))
        res = res * 10 + ch - '0', ch = getchar();
    return f ? -res : res;
}

const int N = 5003;
int n, a[N][N], lft[N][N], dwn[N][N], cnt, L[N], R[N];

// 检查是否存在大小为K的三角形
bool check(int K, int st, int St) {
    static int stk[N];
    int top = 0;
    
    for (int i = 1; i <= cnt; ++i) {
        // 维护滑动窗口
        if (i > K) {
            while (top && R[stk[top]] < R[i - K])
                --top;
            stk[++top] = i - K;
        }
        
        // 弹出不满足条件的元素
        while (top && R[stk[top]] < i + St)
            --top;
            
        // 检查是否找到满足条件的三角形
        if (top && L[i] <= stk[top] + st)
            return 1;
    }
    return 0;
}

int main() {
    n = read();
    
    // 读入数据
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            a[i][j] = read();
    
    // 预处理向左第一个损坏位置
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            lft[i][j] = !a[i][j] ? lft[i][j - 1] : j;
    
    // 预处理向下第一个损坏位置
    for (int i = 1; i <= n; ++i)
        dwn[n + 1][i] = n + 1;
    for (int i = n; i; --i)
        for (int j = 1; j <= i; ++j)
            dwn[i][j] = !a[i][j] ? dwn[i + 1][j] : i;
    
    int ans = 0;
    
    // 主循环：按对角线扫描
    for (int i = 1; i <= n; ++i) {
        for (int j = i, k; j <= n; j = k + 1) {
            k = j;
            if (a[j][j - i + 1]) continue;
            
            // 收集连续完好的对角线段
            L[cnt = 1] = lft[j][j - i + 1] + 1;
            R[cnt] = dwn[j][j - i + 1] - 1;
            
            while (k < n && !a[k + 1][k + 2 - i]) {
                ++k;
                L[++cnt] = lft[k][k - i + 1] + 1;
                R[cnt] = dwn[k][k - i + 1] - 1;
            }
            
            // 二分查找最大三角形大小
            while (check(ans, j - i, j - 1))
                ++ans;
        }
    }
    
    // 输出三角形面积（水晶数量）
    cout << 1ll * (ans + 1) * ans / 2 << endl;
    return 0;
}

算法正确性

预处理的意义

• lft[i][j]：确定了三角形左边界的位置
• dwn[i][j]：确定了三角形下边界的位置
• 这两个数组共同定义了每个位置能形成的最大三角形范围

检查函数的逻辑

check 函数使用单调栈维护一个滑动窗口，确保：

1. 三角形的左边界不超过损坏位置
2. 三角形的下边界不超过损坏位置
3. 三角形内部没有损坏的水晶

复杂度分析

• 预处理：$O(n^2)$
  • 计算 lft 和 dwn 数组
• 主算法：$O(n^2 \log n)$ 或 $O(n^2)$
  • 外层循环 $O(n)$
  • 内层循环均摊 $O(n)$
  • check 函数 $O(n)$

样例验证

样例1

输入：
2
0
1 0
输出：1

正确：只能选择单个水晶。

样例2

输入：
5
0
0 0
0 0 1
0 1 0 0
0 0 0 0 1
输出：10

正确：找到大小为4的三角形，面积 $4×5/2=10$。

总结

本题的解法体现了以下技巧：

1. 预处理优化：通过预处理边界信息加速查询
2. 对角线扫描：利用三角形矩阵的特殊结构
3. 滑动窗口：使用单调栈维护候选解
4. 二分答案：高效确定最大可行大小

这种结合预处理和扫描线的方法，对于解决矩阵中的几何模式匹配问题具有很好的参考价值。