题解：P6143 [USACO20FEB] Equilateral Triangles P

· · 题解

题目链接

洛谷 P6143 [USACO20FEB] Equilateral Triangles P

思路分析

旋转方阵

通过旋转方阵四次，可以确保所有可能的等边三角形都被考虑到了。这是因为等边三角形在不同方向上的表现形式可以通过旋转统一起来。

前缀和优化

使用前缀和数组 f 来加速计算符合条件的第三个顶点的数量。这样可以在 O(1) 时间内计算出任意矩形区域内的奶牛数量。

枚举和判断

对于每一个有奶牛的位置 (i, j)，枚举可能的等边三角形的另一个顶点 (x, y)，并通过前缀和数组计算符合条件的第三个顶点的数量。

复杂度分析

时间复杂度

空间复杂度

总结

通过旋转方阵和前缀和优化，我们可以有效地计算出方阵中所有等边三角形的数量。这种方法不仅简单易懂，而且具有较高的效率，能够处理较大的输入规模。

进一步解释

关键概念：曼哈顿距离与等边三角形

曼哈顿距离定义为两点之间的水平距离加上垂直距离。对于等边三角形，我们需要找到三头奶牛，使得它们之间的曼哈顿距离相等。 图片来自题解区第一篇

图解说明

考虑一个斜向下 45 度的直线，假设我们在这条直线上找到了两点 J 和 K。我们可以构造一个等腰直角三角形 \triangle JHK，并延长 JH 和 KH 构造另一个等腰直角三角形 \triangle OHL。如果 O 和 L 也是奶牛的位置，那么 J, K, O 和 L 可以构成多个等边三角形。

实现细节

前缀和数组

我们使用前缀和数组 f 来加速计算。对于每个位置 (i, j)，f[i][j] 存储从 (1, 1) 到 (i, j) 的所有奶牛数量。

旋转方阵

通过旋转方阵四次，确保所有方向的等边三角形都被考虑到了。

枚举和判断

对于每个有奶牛的位置 (i, j)，我们枚举可能的等边三角形的另一个顶点 (x, y)，并通过前缀和数组计算符合条件的第三个顶点的数量。

代码实现

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

const int N = 1e3 + 5; // 定义方阵的最大尺寸
int n; // 方阵的大小
int ans = 0; // 记录等边三角形的数量
int a[N][N]; // 原始方阵
int b[N][N]; // 用于临时存储方阵的副本
int f[N][N]; // 前缀和数组

// 旋转方阵 90 度
void rotateMatrix() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            b[i][j] = a[i][j]; // 复制原始方阵到临时方阵
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            a[i][j] = b[n - j + 1][i]; // 旋转方阵
        }
    }
}

// 计算当前状态下等边三角形的数量
void calculateEquilateralTriangles() {
    memset(f, 0, sizeof(f)); // 初始化前缀和数组
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][j - 1] + a[i][j]; // 右下45度的前缀和
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 0) continue; // 如果当前位置没有奶牛，跳过
            for (int k = 1; k <= n; k++) {
                int x = i + k, y = j + k; // 枚举可能的等边三角形的另一个顶点
                if (x > n || y > n) break; // 如果超出方阵范围，跳出循环
                if (a[x][y] == 0) continue; // 如果当前位置没有奶牛，跳过
                int m1 = max(0, i + 2 * k - n); // 计算前缀和的边界
                ans += f[min(n, i + 2 * k)][j - m1] - f[x][max(0, j - k)]; // 更新等边三角形的数量
            }
        }
    }
}

int main() {
    cin >> n; // 读取方阵的大小
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            char c;
            cin >> c; // 读取方阵中的每个元素
            if (c == '*') {
                a[i][j] = 1; // 如果是奶牛，标记为 1
            }
        }
    }

    for (int i = 1; i <= 4; i++) { // 旋转四次，每次 90 度
        rotateMatrix(); // 旋转方阵
        calculateEquilateralTriangles(); // 计算等边三角形的数量
    }

    cout << ans; // 输出结果
}

结论

通过上述方法，我们可以高效地解决这个问题，并确保所有可能的等边三角形都被考虑到了。这种方法在时间和空间复杂度上都表现良好，能够处理较大的输入规模。