自动搬运

查看原文

来自洛谷，原作者为

	hyfhaha AFO. 再见了，OI

搬运于2025-08-24 22:17:51，当前版本为作者最后更新于2020-05-21 15:08:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 P6143 【[USACO20FEB]Equilateral Triangles P】

本题解所涉及知识点仅有前缀和。

其实也不需要什么曼哈顿距离的转化，有些结论还是显而易见的

)

如上图，对于斜向下$45°$的直线上任意两个点（图中$J,K$）两点

向下做等腰直角三角形$\triangle JHK$ 并延长$JH$和$KH$ 做的等腰直角三角形$\triangle OHL$

使$\triangle OHL \cong \triangle JHK$

那么线段$OL$上任意一个整点(如图$O,N,M,L$)与$J,K$两点一定形成一个曼哈顿等边三角形

证明：首先$\triangle OJK$ 一定是曼哈顿等边三角形（易证）

$O$每次延$OL$向下移动一个点，它与$J,K$的曼哈顿距离不变（横$+1$，纵$-1$）

所以线段$OL$上任意一个整点与$J,K$两点都可形成曼哈顿等边三角形

上面的结论非常显然，我们可以根据上面的结论解决此题

我们先对每一条斜向下的直线做一个前缀和，这样我们可以快速计算出一条斜线段上有多少个*点

然后我们枚举一个*点（图中$J$）和一个距离（如图中线段$JH$的长）

辣么我们就可以知道其他$3$个点的坐标了（如图上：$K,O,L$）

如果判断点（图中的$K$）也是*点

就用前缀和算出线段（图中$OL$）上*点的数量

累加答案。

但是，明显我们要统计的不止斜向下$45°$这一条直线的一边上的曼哈顿等边三角形。

所以我们把整张图翻转$90°$，再做一遍。同理$180°$和$270°$ 也要再做一遍。

为了避免重复计算，我们前缀和统计答案时要减去左端点（即$f(R)-f(L-1)$变为$f(R)-f(L)$）

其实核心思想很简单，但我好像解释得太复杂了……

看代码吧，核心的前缀和就一条式子

#include<bits/stdc++.h>
#define maxn 611
using namespace std;
int a[maxn][maxn],b[maxn][maxn],n,f[maxn][maxn],ans,tot;
struct kkk{
	int x;int y;
}p[maxn*maxn];
void turn(){			//把图翻转90°
	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[j][i]=b[n-i+1][j];
	}
}
void solve(){			//统计答案
	tot=0;
	for(int i=1;i<=n*2;i++)for(int j=1;j<=n*2;j++)f[i][j]=0;
	for(int i=1;i<=n*2;i++){	//开两倍是为了防溢出
		for(int j=1;j<=n*2;j++){
			f[i][j]=f[i-1][j+1]+a[i][j];
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(a[i][j]==1)p[++tot].x=i,p[tot].y=j;	//标记*点
	for(int i=1;i<=tot;i++){	//枚举*点
		for(int k=1;k<=n;k++){	//枚举距离
			int xa=p[i].x,ya=p[i].y;
			int xb=p[i].x-k,yb=p[i].y+k;	//判断点坐标
			if(xb<1||yb>n)break;	//超出范围判断
			if(a[xb][yb]==0)continue;	//判断点是否是*点
			ans+=f[xa+k][ya+k]-f[xa][ya+k*2];	//前缀和统计答案
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char ch;
			cin>>ch;
			if(ch=='*')a[i][j]=1;
			else a[i][j]=0;
		}
	}
	for(int i=1;i<=4;i++)turn(),solve();//翻转一次，统计一次
	printf("%d\n",ans);	//输出
	return 0;
}

好简洁的呢

时间复杂度$O(4*n^3)$，不过应该比较难跑满，好像还挺快的（雾