P9944 题解
题意：每次加入一头牛，统计此时恰好有三头牛相邻的牛的数量。
思路：
- 每次按题意枚举符合要求的牛的数量，每次都需要枚举所有牛，明显超时。
- 考虑到每次加入后只可能会改变加入的牛以及相邻的牛的情况，所以只需每次操作后更新答案即可，时间复杂度
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;
}
}