比赛 2025暑期集训第6场 评测结果 AAAAAAAAAAAAAAA
题目名称 Equilateral Triangles 最终得分 100
用户昵称 Hollow07 运行时间 1.370 s
代码语言 C++ 内存使用 21.02 MiB
提交时间 2025-07-12 12:32:36
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll N=1010;
char s;
ll n,a[N][N],b[N][N],f[N][N],ans,cnt;
struct node{
	ll x,y;
}p[N*N];

int main(){
	freopen("usaco_Feb_Triangles!.in","r",stdin);
	freopen("usaco_Feb_Triangles!.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>s;
			if(s=='*') a[i][j]=1;
		}
	}
	for(int i=1;i<=4;i++){
		cnt=0;
		memset(b,0,sizeof(b));
		memset(f,0,sizeof(f));
		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];
			}
		}
		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[++cnt].x=i;
					p[cnt].y=j;
				}
			}
		}
		for(int i=1;i<=cnt;i++){
			for(int k=1;k<=n;k++){
				ll xa=p[i].x,ya=p[i].y;
				ll 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];
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}