自动搬运

查看原文

来自洛谷，原作者为

	tallnut 楼头残梦五更钟，花底离愁三月雨

搬运于2025-08-24 23:05:21，当前版本为作者最后更新于2024-10-20 14:19:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

好题。

思路

首先把湖的信息存在二维数组里面。由于题目保证所有湖不重叠，因此复杂度是 $\Theta(nm)$ 的。

为了按照时间顺序处理操作，使用优先队列存储事件。一个事件包含 $4$ 种信息：

• 发生时间；
• 是哪种事件：生成了一颗新树，还是一棵树死亡；
• 发生地点：$x$ 坐标；
• 发生地点：$y$ 坐标。

然后把这些事件按照时间排序放进优先队列里面，每次取出堆顶即可做到根据时间的推移模拟事件的发生过程。

考虑如何处理这些事件。

• 生成了一棵树：在地图上标记这棵树，然后将它死亡的信息放入堆中。（如果它身边有湖或者有其他树，则永远不会死，因为它和另外那棵树可以互相保护。）若当前时间是 $t$，则它死亡的时间应当是 $t+k+0.5$（因为题目中说大于 $k$ 秒后，但在下一秒之前），但为了避免出现浮点数，可以把所有时间乘以 $2$ 存储起来。随后向四个方向扩展，判断是否符合题目中生成树的要求。
• 一棵树死亡：判断它身边是否有湖或树，没有则移除这棵树。

于是就做完了这道题。算上堆的时间，时间复杂度为 $\Theta(nm\log(nm))$。

记得开 long long。

AC 代码

场上没开 long long 痛失 $40$ 分。/fn

/*
用优先队列模拟事件发生的顺序
*/
// NOTE: "[EDIT]" means you should edit this part by yourself
#include <bits/stdc++.h>
// [EDIT] please enable this line if there are many tests
//#define MULTITEST
using namespace std;
// [EDIT] if you want to copy some templates, please paste them here

typedef long long ll;
#define int ll
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
#define rep2(i,x,y) for (int i = (x);i >= (y);i--)
#define rep3(i,x,y,z) for (int i = (x);i <= (y);i += (z))
#define rep4(i,x,y,z) for (int i = (x);i >= (y);i -= (z))
#define cl(a) memset(a,0,sizeof(a))
// [EDIT] define some constants here
const int N = 3010;
// [EDIT] define some variables, arrays, etc here
struct happening
{
	//存储：乘以2的值
	int t;
	//0表示生长出一棵树，1表示这棵树死亡
	int thing;
	//x,y坐标
	int x;
	int y;
	bool operator<(const happening& xx) const { return t > xx.t; }
} tmp;
int n,m,qq,r,k,aa,bb,cc,dd,tt,xx,yy,ans;
priority_queue<happening> q;
//0表示啥都没有，1表示有水，2表示有树
int mp[N][N];
inline bool check_grow(int x,int y) { return x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] == 0 && (mp[x - 1][y] == 1 || mp[x + 1][y] == 1 || mp[x][y - 1] == 1 || mp[x][y + 1] == 1); }
// [EDIT] a function to solve the problem
void solve()
{
    //input
	cin >> n >> m >> qq >> r >> k;
	k *= 2;
	rep1(i,1,qq)
	{
		cin >> aa >> bb >> cc >> dd;
		rep1(j,aa,cc)
			rep1(kk,bb,dd)
				mp[j][kk] = 1;
	}
	rep1(i,1,r)
	{
		cin >> tt >> xx >> yy;
		q.push({tt * 2,0,xx,yy});
	}
    //solve
	while (q.size())
	{
		tmp = q.top();
		q.pop();
		//判断是什么事件
		//是树生长的事件
		if (tmp.thing == 0)
		{
			//判断；这个格子上面没树
			if (mp[tmp.x][tmp.y] == 0)
			{
				mp[tmp.x][tmp.y] = 2;
				//如果他旁边没树且没水：那么加入死亡事件，否则他们俩可以互相固定，都不会死
				if (mp[tmp.x - 1][tmp.y] == 0 && mp[tmp.x + 1][tmp.y] == 0 && mp[tmp.x][tmp.y - 1] == 0 && mp[tmp.x][tmp.y + 1] == 0)
					q.push({tmp.t + k + 1,1,tmp.x,tmp.y});
				//向旁边扩展
				if (check_grow(tmp.x - 1,tmp.y))
					q.push({tmp.t + 2,0,tmp.x - 1,tmp.y});
				if (check_grow(tmp.x + 1,tmp.y))
					q.push({tmp.t + 2,0,tmp.x + 1,tmp.y});
				if (check_grow(tmp.x,tmp.y - 1))
					q.push({tmp.t + 2,0,tmp.x,tmp.y - 1});
				if (check_grow(tmp.x,tmp.y + 1))
					q.push({tmp.t + 2,0,tmp.x,tmp.y + 1});
			}
		}
		//是树死亡的事件
		else if (tmp.thing == 1)
		{
			//判断：都是陆地
			if (mp[tmp.x - 1][tmp.y] == 0 && mp[tmp.x + 1][tmp.y] == 0 && mp[tmp.x][tmp.y - 1] == 0 && mp[tmp.x][tmp.y + 1] == 0)
				mp[tmp.x][tmp.y] = 0;
		}
	}
	rep1(i,1,n)
		rep1(j,1,m)
			if (mp[i][j] == 2)
				ans++;
    //output
	cout << ans;
    //clear

}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif
    while (t--)
        solve();
}