P6143 [USACO20FEB] Equilateral Triangles P 题解

前情提要

本蒟蒻的思路跟各路神犇大差不差，主要是看到题解区关于曼哈顿距离下等边三角形的结论证明比较简略，所以我写了一个详细一点的，这篇题解也主要围绕结论的证明。

曼哈顿距离

顾名思义，曼哈顿距离的名称源于纽约曼哈顿区的网格状街道布局，行人只能沿水平或垂直方向移动，无法斜穿建筑。‌‌

用数学语言表达，点 $A(x_a,y_a)$ 和点 $B(x_b,y_b)$ 的曼哈顿距离等于 $|x_a-x_b|+|y_a-y_b|$，我们姑且将其记作 $d(A, B)$。

根据题意，题目让我们找到农场里有多少个“曼哈顿距离下的等边三角形”（或者我们先叫它曼哈顿等边三角形）。详细来说，假设我们有“曼哈顿等边三角形”$ABC$，其中点 $A(x_a,y_a)$、点 $B(x_b,y_b)$、点 $C(x_c,y_c)$，满足：

$$d(A,B) = d(B,C) = d(A,C)$$

即：

$$|x_a-x_b|+|y_a-y_b| = |x_b-x_c|+|y_b-y_c| = |x_a-x_c|+|y_a-y_c|$$

这很显而易见，对吧。

这个时候我们还不知道这个三角形会有什么特殊的性质，但是我们可以先画出来，再观察它的条件：

对于平面坐标系 $xOy$ 中任意 $\triangle ABC$，若满足 $d(A,B)=d(B,C)=d(A,C)$，即 $AD+BD=AE+EC=CF+BF$，该三角形为“曼哈顿等边三角形”。这也非常显而易见。

发现结论

隐隐约约感觉这三条曼哈顿距离总有一些联系，我们可以用等量关系表示一下这几条线段

由图，$BD=BF+CF-AD$，又因为 $BF-AD=AE$，所以 $BD=AE+CF$。

我们又知 $CE=BD-CF$，可得 $CE=AE$。

神奇的事情发生了，$CE=AE$。因为我们已知 $\angle E$ 一定为直角，故 $\triangle ACE$ 一定是等腰直角三角形。

因为在这个题目中所有的奶牛都在整点位置上，所以 $AC$ 一定在斜向 $45\degree$ 的直线上排布。

但是我们并不确定点 $A$ 和点 $C$ 的位置关系，因此会产生两种情况：

这个时候这个题目的大致思路就出来了：枚举斜向直线上的点 $A$，同时枚举相对应的点 $C$，计算满足条件的点 $B$ 有多少个。

前缀和优化

如果你按照上面的步骤写下来，就会发现，找点 $B$ 的数量非常麻烦，咋办？

众所周知，前缀和是个好东西，但是怎么把它用在斜线上呢？

那就斜着算呗，于是就有了斜向前缀和。斜向前缀和可以高效统计对角线方向上的元素和。在本题中，我们需要快速计算特定对角线区间内的奶牛数量，这正是斜向前缀和擅长的地方。

不难得出斜向前缀和的状态转移方程：

$$s_{i,j}=s_{i-1,j+1}+a_{i,j}$$

实际上不难理解，点 $(i,j)$ 的斜向前缀和就是从它左上方来的前缀和加上自己这个点的数。也不一定是左上方，只要是斜向 $45\degree$ 都可以。

但如果只用这一个式子，是只能算左斜方的斜向前缀和，右斜方被遗忘了。这个时候有两条路：

1. 多列式子，算 $4$ 遍
2. 简单粗暴，把整个网格转 $90\degree$

我们选择第二条路。

关于矩阵的旋转不再赘述，详细看下面这张图（太丑了凑合看吧）：

就这样暴力转几次就可以统计全了，答案就是 $s_{x+d,y+d} - s_{x,y+d\times2}$ 的累加和。

您最想要的代码在这呢

时间复杂度 $O(n^3)$，按题目给的数据量肯定能过。

#include <bits/stdc++.h>
#define pii pair<int, int>
#define rei for (int i = 1; i <= n; ++i)
#define rej for (int j = 1; j <= n; ++j)
#define fst first
#define scd second
using namespace std;

const int maxn = 614;
int a[maxn][maxn], tmp[maxn][maxn], s[maxn*2][maxn*2];
int n, idx, ans, t = 4;
char c;
pii p[maxn * maxn];

// 顺时针旋转90度
void rotate() {
    rei rej tmp[i][j] = a[i][j];
    rei rej a[j][n-i+1] = tmp[i][j];
}

int main() {
    cin >> n;
    // 初始化数组
    memset(a, 0, sizeof(a));
    memset(tmp, 0, sizeof(tmp));
    memset(s, 0, sizeof(s));
    
    // 读取输入
    rei rej {
        cin >> c;
        a[i][j] = (c == '*') ? 1 : 0;
    }
    
    while (t--) {
        rotate();
        // 重置索引和前缀和
        idx = 0;
        for (int i = 0; i <= n*2; i++) {
            for (int j = 0; j <= n*2; j++) {
                s[i][j] = 0;
            }
        }        
        // 计算斜向前缀和
        for (int i = 1; i <= n*2; i++) {
            for (int j = 1; j <= n*2; j++) {
                s[i][j] = s[i-1][j+1] + a[i][j];
            }
        }
        
        // 收集所有奶牛位置
        rei rej {
            if (a[i][j]) {
                p[++idx] = {i, j};
            }
        }
        
        // 枚举每个奶牛点A
        for (int i = 1; i <= idx; i++) {
            int ax = p[i].fst, ay = p[i].scd;
            
            // 枚举距离d
            for (int d = 1; d <= n; d++) {
                // 计算点B位置（左上方向）
                int cx = ax - d, cy = ay + d;
                
                // 检查点B是否有效
                if (cx < 1 || cy > n) break; // 你 越 界 了
                if (!a[cx][cy]) continue; // 弄 虚 作 假
                
                // 使用斜向前缀和计算点C的数量
                ans += s[ax+d][ay+d] - s[ax][ay+2*d];
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

码字不易，作图更不易，看完点个赞在走呗。