题解：P11215 【MX-J8-T3】水星湖

tallnut · 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();
}