自动搬运

查看原文

来自洛谷，原作者为

	Harrylzh "Here I wish, Let there be light"

搬运于2025-08-24 22:53:14，当前版本为作者最后更新于2024-01-07 20:10:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：每次加入一头牛，统计此时恰好有三头牛相邻的牛的数量。

思路：

• 每次按题意枚举符合要求的牛的数量，每次都需要枚举所有牛，明显超时。
• 考虑到每次加入后只可能会改变加入的牛以及相邻的牛的情况，所以只需每次操作后更新答案即可，时间复杂度 $O(n)$ 。变量具体更新方法详见代码。

代码：

#include<iostream>
using namespace std;
int n;
bool l[1000+5][1000+5];//记录此位置是否有牛
int l2[1000+5][1000+5];//记录每头牛相邻的牛的数量
int ans=0;//答案
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//相邻的牛的方向
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		l[x][y]=1;//记录此位置有牛
		for(int j=0;j<4;j++)//遍历相邻位置的牛
		{
			if(x+d[j][0]>=0&&y+d[j][1]>=0&&l[x+d[j][0]][y+d[j][1]])//判断此位置是否存在且有牛
			{
				l2[x][y]++;//相邻的牛数加一
				if(l2[x+d[j][0]][y+d[j][1]]==3) ans--;//如果原本这头牛是舒适的，加入后不是了，答案减一
				if(l2[x+d[j][0]][y+d[j][1]]==2) ans++;//如果原本这头牛不是舒适的，加入后是了，答案加一
				l2[x+d[j][0]][y+d[j][1]]++;//相邻牛的相邻数量加一
			}
		}
		if(l2[x][y]==3) ans++;//如果加入这头牛是舒适的，答案加一
		cout<<ans<<endl;
	}
}