专栏文章

题解：P6143 [USACO20FEB] Equilateral Triangles P

EELECTRODE_kaf
P6143题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq9znti
此快照首次捕获于
2025/12/04 01:23
3 个月前
此快照最后确认于
2025/12/04 01:23
3 个月前
查看原文
本题解中称牛为“点”，D(A,B)D(A,B) 表示点 AA 与点 BB 的曼哈顿距离。
先讲做法再讲成立的理由。

做法

枚举两个连线平行于 y=xy=x 的点（图中黑点），则图中红线范围内的点都符合要求，用前缀和累加。
每次旋转图形 90°90°，对 44 种方向都计算一遍。

正确性说明

首先考虑一对点 A,BA,B，对于 AA 来说，满足 D(A,B)=D(A,C)D(A,B)=D(A,C) 的点一定在两条平行于 y=xy=x 的直线 l1,l2l_1,l_2 上。对 BB 同理，存在 l3,l4l_3,l_4。但是只有在 ABAB 连线平行于 y=xy=x 时 l1l_1 与 l3l_3；l2l_2 与 l4l_4 才会重合，即存在“等边三角形”。但上述情况在各种角度下均成立，故累加时需要旋转。
细节：红线的两个端点应该只计算一个，因为另一个可以和两个黑点中的一个作为新的黑点，算进去的这个红点仍作为红点，这样会在另一种角度中被认为是一种新的方案。前缀和注意溢出问题。
CPP
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;
}
代码宏定义在我个人空间自取。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...