自动搬运

查看原文

来自洛谷，原作者为

	Qura **

搬运于2025-08-24 21:36:16，当前版本为作者最后更新于2018-07-19 20:42:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

什么？我暴力模拟A了？

预处理出每个底边端点的四个方向可延伸的最大长度。然后枚举底边判断是否构成三角形即可。(图：四个方向)

接下来就是喜闻乐见的代码

#include <cstdio>
const int N=1000+10;
struct data {
	bool l,r,d;
	void read() {
		scanf("%d%d%d",&l,&r,&d);
	}
} a[N][N];
int n,lu[N][N],ld[N][N],ru[N][N],rd[N][N];
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=i; ++j) {
			a[i][j].read();
		}
	}
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=i; ++j) {
			if(a[i][j].l) lu[i][j]=lu[i-1][j]+1;
			if(a[i][j].r) ru[i][j]=ru[i-1][j-1]+1;
		}
	}
	for(int i=n; i; --i) {
		for(int j=i; j; --j) {
			if(a[i+1][j].r) ld[i][j]=ld[i+1][j+1]+1;
			if(a[i+1][j+1].l) rd[i][j]=rd[i+1][j]+1;
		}
	}
	int ans=0;
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) {
			for(int k=j; a[i][k].d && k<=n && (k-j+1)<=lu[i][j]; ++k) {
				ans+=(k-j+1)<=ru[i][k];
			}
			for(int k=j; a[i][k].d && k<=n && (k-j+1)<=ld[i][j]; ++k) {
				ans+=(k-j+1)<=rd[i][k];
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}