比赛 USACO铂金组&NOIonline模拟赛 评测结果 AAAAAAAAAAAAAAA
题目名称 Equilateral Triangles 最终得分 100
用户昵称 梦那边的美好ET 运行时间 6.577 s
代码语言 C++ 内存使用 14.76 MiB
提交时间 2020-03-03 09:28:35
显示代码纯文本
#include<bits/stdc++.h>
#define maxn 310
#define LL long long
using namespace std;
int n,a[maxn][maxn],sum1[maxn][maxn],sum2[maxn][maxn],sum;
char s[maxn];
LL ans;
void solve1(int x,int y,int l){
    int p=x-l,q=y-l;
    if(p<=0||q<=0||!a[p][y]||!a[x][q])return;
    int a1=min(n-x,l),a2=min(n-y,l);
    if(a1+a2<l)return;
    ans+=(LL)(sum2[x+a1][y+l-a1]-sum2[x+l-a2-1][y+a2+1]);
    return;
}
void solve2(int x,int y,int l){
    int p=x-l,q=y+l;
    if(p<=0||q>n||!a[p][y]||!a[x][q])return;
    int a1=min(n-x,l),a2=min(y-1,l);
    if(a1+a2<l)return;
    ans+=(LL)(sum1[x+a1][y-l+a1]-sum1[x+l-a2-1][y-a2-1]);
    return;
}
void solve3(int x,int y,int l){
    int p=x+l,q=y+l;
    if(p>n||q>n||!a[p][y]||!a[x][q])return;
    int a1=min(x-1,l),a2=min(y-1,l);
    if(a1+a2<l)return;
    ans+=(LL)(sum2[x-l+a2][y-a2]-sum2[x-a1-1][y-l+a1+1]);
    return;
}
void solve4(int x,int y,int l){
    int p=x+l,q=y-l;
    if(p>n||q<0||!a[p][y]||!a[x][q])return;
    int a1=min(x-1,l),a2=min(n-y,l);
    if(a1+a2<l)return;
    ans+=(LL)(sum1[x-l+a2][y+a2]-sum1[x-a1-1][y+l-a1-1]);
    return;
}
int main(){
	freopen("usaco_Feb_Triangles!.in","r",stdin);
	freopen("usaco_Feb_Triangles!.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=n;j++)a[i][j]=(s[j]=='*');
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) 
            sum1[i][j]=sum1[i-1][j-1]+a[i][j],
            sum2[i][j]=sum2[i-1][j+1]+a[i][j];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                solve1(i,j,k);solve2(i,j,k);solve3(i,j,k);solve4(i,j,k);
                sum=(i>k&&a[i-k][j])+(j+k<=n&&a[i][j+k])+(i+k<=n&&a[i+k][j])+(j>k&&a[i][j-k]);
                ans-=(LL)(sum==3?1:(sum==4?4:0));
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}