题解 P6143 【[USACO20FEB]Equilateral Triangles P】
hyfhaha
·
·
题解
题解 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 一定是曼哈顿等边三角形（易证）
所以线段$OL$上任意一个整点与$J,K$两点都可形成曼哈顿等边三角形
------
上面的结论非常显然，我们可以根据上面的结论解决此题
我们先对每一条斜向下的直线做一个前缀和，这样我们可以快速计算出一条斜线段上有多少个`*`点
然后我们枚举一个`*`点（图中$J$）和一个距离（如图中线段$JH$的长）
辣么我们就可以知道其他$3$个点的坐标了（如图上：$K,O,L$）
如果判断点（图中的$K$）也是`*`点
就用前缀和算出线段（图中$OL$）上`*`点的数量
累加答案。
但是，明显我们要统计的不止斜向下$45°$这一条直线的一边上的曼哈顿等边三角形。
所以我们把整张图翻转$90°$，再做一遍。同理$180°$和$270°$ 也要再做一遍。
为了避免重复计算，我们前缀和统计答案时要减去左端点（即$f(R)-f(L-1)$变为$f(R)-f(L)$）
其实核心思想很简单，但我好像解释得太复杂了……
看代码吧，核心的前缀和就一条式子
```cpp
#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)$，不过应该比较难跑满，好像还挺快的（雾