BZOJ1201 [HNOI2005]数三角形 大力出奇迹

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

---

题目传送门 - BZOJ1201

---

题意概括

　　

---

题解

　　n跑过去了，大力出奇迹！简单的，不多说了。

---

代码

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=1000+5;

void read(int &x){

    x=0;

    char ch=getchar();

    while (!('0'<=ch&&ch<='9'))

        ch=getchar();

    while ('0'<=ch&&ch<='9')

        x=x*10+ch-48,ch=getchar();

}

struct Tri{

    int a,b,c;

    void Read(){

        read(a),read(b),read(c);

    }

}t[N][N],sum[N][N];

int n;

int main(){

    scanf("%d",&n);

    for (int i=1;i<=n;i++)

        for (int j=1;j<=i;j++)

            t[i][j].Read();

    memset(sum,0,sizeof sum);

    for (int i=1;i<=n;i++)

        for (int j=1;j<=i;j++){

            sum[i][j].a=sum[i-1][j].a+t[i][j].a;

            sum[i][j].b=sum[i-1][j-1].b+t[i][j].b;

            sum[i][j].c=sum[i][j-1].c+t[i][j].c;

        }

    int ans=0;

    for (int i=1;i<=n;i++)

        for (int j=1;j<=i;j++){

            for (int k=0;i+k<=n;k++){

                if (!t[i+k][j].a||!t[i+k][j+k].b)

                    break;

                if (sum[i+k][j+k].c-sum[i+k][j-1].c==k+1)

                    ans++;

            }

            for (int k=0;;k++){

                int ii=i-k,jj=j-k-1;

                if (jj>ii||ii<1||jj<1||j>ii||!t[ii][jj].b||!t[ii][j].a)

                    break;

                if (sum[ii-1][j-1].c-sum[ii-1][jj-1].c==k+1)

                    ans++;

            }

        }

    printf("%d\n",ans);

    return 0;

}