CodeForces-738B Spotlight 题解

昨天写了这题,很悲催的是我发现爆搜炸了,于是我想到了预处理的方法。

具体思路很简单:先循环录入整个舞台布局,放到stage_s[0]里面,第一个坐标是(1,1),我把(0,x)与(x,0)都空下来,分别存储每列每行的演员个数。
随后,我要开始计算每个点四个方向的演员数量,分别在stage_s[1]、[2]、[3]、[4]里面。具体计算其实很简单,对于(x,y),往上就是(x-1,y)往上的演员数加上(x-1,y)自身值,往下就是(0,y)的值(这一列总数)减去(x,y)往上的演员数减去(x,y)自身值,往左往右同理,但是要记住上、左两个方向要特判0。
最后就很简单了,直接加就可以了,我代码是因为之前辣鸡的暴力代码(暴力并没有出奇迹,它TLE了)有用到,所以就写函数了,其实不用。

#include<bits\stdc++.h>

int n,m,ans=0;
int stage_s[5][1002][1002]; //0舞台,1往上,2往下,3往左,4往右 
//stage_s[1][1][1] 表示1,1向上(不包括1,1)有几个人 
using namespace std;

int is_good(int a,int b)
{
	int temp=0;
	if(!stage_s[0][a][b])
	{ 
		//往上
		if(stage_s[1][a][b])temp++;
		//往下 
		if(stage_s[2][a][b])temp++;
		//往左 
		if(stage_s[3][a][b])temp++;
		//往右 
		if(stage_s[4][a][b])temp++;
	}
	return temp;
}

int main()
{
	ios::sync_with_stdio(false);
	memset(stage_s,0,sizeof(stage_s));
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		int temp=0;
		for(int j=1;j<=m;j++)
		{
			cin >> stage_s[0][i][j];
			temp+=stage_s[0][i][j];
		}
		stage_s[0][i][0]=temp;
	}
	for(int j=1;j<=m;j++)
	{
		int temp=0;
		for(int i=1;i<=n;i++)
		{
			temp+=stage_s[0][i][j];
		}
		stage_s[0][0][j]=temp;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(i!=1)stage_s[1][i][j]=stage_s[1][i-1][j]+stage_s[0][i-1][j];//会碰到0
			stage_s[2][i][j]=stage_s[0][0][j]-stage_s[0][i][j]-stage_s[1][i][j];
			if(j!=1)stage_s[3][i][j]=stage_s[3][i][j-1]+stage_s[0][i][j-1];//会碰到0
			stage_s[4][i][j]=stage_s[0][i][0]-stage_s[0][i][j]-stage_s[3][i][j];
			ans+=is_good(i,j);
		}
	}
	cout << ans << endl;
	return 0;
} 

留下你的评论呗...

电子邮件地址不会被公开。 必填项已用*标注