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

· · 题解

好像有点麻烦了。

思路分析

我们开一个二维数组表示地图，湖泊为 1，树木为 2。对于湖泊的标记，可以用二维差分来做，时间复杂度 O(nm)。

我们发现，一个地图中只存在三种事件发生。

我们可以将每个事件用四元组 (op,t,x,y) 表示，这四个元素分别表示事件类型，发生时间，发生位置，然后把他们按照时间执行即可

同时，事件一的发生可能会导致事件二和事件三的出现，事件二的发生可能会导致新的事件二和事件三的出现，所以我们需要一个数据结构，支持插入一个任务，并取出时间最小的任务，显然可以优先队列，时间复杂度 O(nm\log nm+nm)。

不过仍然有点慢，我们考虑用三个不同的队列维护三堆不同的任务，这样不需要数据结构就可以确保单调性。初始时只有队列 1 有任务，每次查找当前时间最小的事件，就对比三个队头，返回时间最小的（如果存在时间相同则优先返回事件 1,2，最后返回事件 3）。

其他就是一些细节问题了，可以当大模拟练手。

时间复杂度为 O(nm)，可以通过本题。

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N=3005;
int c[N][N],n,m,q,r,k,mp[N][N],fx[]={-1,0,1,0},fy[]={0,1,0,-1},ans;
struct node{
    int t,tim,x,y;
};
queue<node>q1,q2,q3;
void add(int x,int y,int xx,int yy){
    c[x][y]++,c[x][yy+1]--,c[xx+1][y]--,c[xx+1][yy+1]++;
}
node get(){
    if(!q1.size()&&!q2.size()&&!q3.size())return node{-1,0,0,0};//没有任务
    node tmp;
    if(q1.size()&&!q2.size()&&!q3.size())tmp=q1.front(),q1.pop();
    if(!q1.size()&&q2.size()&&!q3.size())tmp=q2.front(),q2.pop();
    if(!q1.size()&&!q2.size()&&q3.size())tmp=q3.front(),q3.pop();
    if(q1.size()&&q2.size()&&!q3.size()){
        if(q1.front().tim<=q2.front().tim)tmp=q1.front(),q1.pop();
        else tmp=q2.front(),q2.pop();
    }
    if(!q1.size()&&q2.size()&&q3.size()){
        if(q2.front().tim<=q3.front().tim)tmp=q2.front(),q2.pop();
        else tmp=q3.front(),q3.pop();
    }
    if(q1.size()&&!q2.size()&&q3.size()){
        if(q1.front().tim<=q3.front().tim)tmp=q1.front(),q1.pop();
        else tmp=q3.front(),q3.pop();
    }
    if(q1.size()&&q2.size()&&q3.size()){
        tmp=q1.front();
        if(tmp.tim>q2.front().tim)tmp=q2.front();
        if(tmp.tim>q3.front().tim)tmp=q3.front();
        if(tmp.t==1)q1.pop();
        if(tmp.t==2)q2.pop();
        if(tmp.t==3)q3.pop();
    }
    return tmp;
}
bool inside(int x,int y){
    return !(x<1||x>n||y<1||y>m);
}//判断是否在地图内
bool check(int x,int y){
    if(!inside(x,y)||mp[x][y]!=0)return 0;
    for(int i=0;i<4;i++){
        int xx=x+fx[i],yy=y+fy[i];
        if(inside(xx,yy)&&mp[xx][yy]==1)return 1;
    }
    return 0;
}//判断能否扩散成树木
bool judge(int x,int y){
    for(int i=0;i<4;i++){
        int xx=x+fx[i],yy=y+fy[i];
        if(inside(xx,yy)&&mp[xx][yy]!=0)return 0;
    }
    return 1;
}//判断会不会死
int main(){
    scanf("%d %d %d %d %d",&n,&m,&q,&r,&k);
    for(int i=1,a,b,c,d;i<=q;i++){
        scanf("%d %d %d %d",&a,&b,&c,&d);
        add(a,b,c,d);//二维差分
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
            if(c[i][j]>=1)mp[i][j]=1;
        }
    }
    for(int i=1,a,b,c;i<=r;i++){
        scanf("%d %d %d",&a,&b,&c);
        q1.push(node{1,a,b,c});
    }
    while(1){
        node t=get();
        if(t.t==-1)break;
        if(t.t==1){
            q2.push(node{2,t.tim,t.x,t.y});
            q3.push(node{3,t.tim+k,t.x,t.y});
            mp[t.x][t.y]=2;
        }else if(t.t==2){
            for(int i=0;i<4;i++){
                int x=t.x+fx[i],y=t.y+fy[i];
                if(check(x,y)){
                    mp[x][y]=2;
                    q2.push(node{2,t.tim+1,x,y});
                    q3.push(node{3,t.tim+k,x,y});
                }
            }
        }else if(t.t==3){
            if(judge(t.x,t.y)){
                mp[t.x][t.y]=0;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]==2)ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

如有错误，请指出。