题解：P6143 [USACO20FEB] Equilateral Triangles P

· · 题解

本题解中称牛为“点”，D(A,B) 表示点 A 与点 B 的曼哈顿距离。

先讲做法再讲成立的理由。

做法

枚举两个连线平行于 y=x 的点（图中黑点），则图中红线范围内的点都符合要求，用前缀和累加。

每次旋转图形 90°，对 4 种方向都计算一遍。

正确性说明

首先考虑一对点 A,B，对于 A 来说，满足 D(A,B)=D(A,C) 的点一定在两条平行于 y=x 的直线 l_1,l_2 上。对 B 同理，存在 l_3,l_4。但是只有在 AB 连线平行于 y=x 时 l_1 与 l_3；l_2 与 l_4 才会重合，即存在“等边三角形”。但上述情况在各种角度下均成立，故累加时需要旋转。

细节：红线的两个端点应该只计算一个，因为另一个可以和两个黑点中的一个作为新的黑点，算进去的这个红点仍作为红点，这样会在另一种角度中被认为是一种新的方案。前缀和注意溢出问题。

const ll N = 500;
ll n, ps[N][N], ans;
bool a[N][N], _a[N][N];
vector<pll> v;

ll Ps(ll x, ll y) {
    if (x > n) {
        y += x - n;
        x = n;
    }
    elif(x < 1) {
        y -= 1 - x;
        x = 1;
    }

    if (y >= 1 and y <= n)
        return ps[x][y];
    else
        return 0;
}

int main() {
    cin >> n;

    rep(i, 1, n) {
        rep(j, 1, n) {
            char in;
            cin >> in;
            a[i][j] = in == '*';
        }
    }

    rep(c, 1, 4) {
        v.clear();
        memset(ps, 0, sizeof(ps));

        rep(i, 1, n) {
            rep(j, 1, n) {
                if (a[i][j])
                    v.pb({i, j});
            }
        }
        rep(i, 1, n) {
            rep(j, 1, n) ps[i][j] = a[i][j] + ps[i - 1][j + 1];//右上角方向的前缀和
        }

        for (pll i : v) {
            rep(j, 1, n) {
                //枚举纵向距离 j

                ll ii = i.fi - j, jj = i.se + j;

                if (ii<1 or jj>n or a[ii][jj] == 0)
                    ctn;

                ans += Ps(i.fi + j, i.se + j) - Ps(i.fi, i.se + j + j);
            }
        }

        rep(i, 1, n) {
            rep(j, 1, n) _a[i][j] = a[i][j];
        }

        //顺时针旋转 90°
        for (ll i1 = 1, j2 = n; i1 <= n; i1++, j2--) {
            for (ll j1 = 1, i2 = 1; j1 <= n; j1++, i2++)
                a[i1][j1] = _a[i2][j2];
        }
    }

    cout << ans;
}

代码宏定义在我个人空间自取。