依旧是模拟赛赛题。

Hint

Analysis

首先你注意到两棵相邻的树是一定不会死的，所以可能会死的只有自己种下去的树，队列维护。

接着考虑对于每个位置， \(\text{bfs}\) 维护一个最小的长出树的时间 \(vis[i][j]\)，最后暴力统计答案即可。

具体细节看注释。

Code

<code>#include<bits/stdc++.h>

#define pb push_back

#define is insert

#define fi first

#define se second

#define mkp make_pair

#define mathmod(a,m) (((a)%(m)+(m))%(m))

#define mem(a,b) memset(a,b,sizeof a)

#define cpy(a,b) memcpy(a,b,sizeof b)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

namespace FastIO{

const int MX=1<<20;

#ifdef ONLINE_JUDGE

char buf[MX],*p1,*p2;

#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MX,stdin),p1==p2)?0:*p1++)

#else

#define gc() getchar()

#endif

char pbuf[MX],*p3=pbuf;

inline void pc(const char c){if(p3-pbuf==MX)fwrite(pbuf,1,MX,stdout),p3=pbuf;*p3++=c;}

inline void flush(){fwrite(pbuf,1,p3-pbuf,stdout),p3=pbuf;}

template<class T> inline void read(T& p){

T x=0,f=1;char c=gc();

while(c<'0'||c>'9'){if(c=='-')f=0;c=gc();}

while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=gc();

p=f?x:-x;

}

template<class T,class ... Args> inline void read(T& p,Args&... args){read(p),read(args...);}

template<class T> inline void write(T x){

if(!x){pc('0');return;}

static short sta[40];short tp=0;

if(x<0) pc('-'),x=-x;

do{sta[tp++]=x%10,x/=10;}while(x);

while(tp) pc(sta[--tp]+'0');

}

template< > inline void write(const char x){pc(x);}

template< > inline void write(const char* x){for(int i=0;x[i];i++)pc(x[i]);}

template< > inline void write(const string x){for(char c:x)pc(c);}

template<class T,class ... Args> inline void write(T x,Args... args){write(x),write(args...);}

#undef gc

}

using namespace FastIO;

const int N=3005;

const int INF=0x7f7f7f7f;

int n,m,q,r,k,tim,cnt,vis[N][N];

int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

short a[N][N];

struct Query{int t,x,y;};

queue<Query> que;

void bfs(Query s){

queue<Query> q;

// 开头也要判断，记得更新 vis

if(vis[s.x][s.y]>s.t) vis[s.x][s.y]=s.t,q.push(s);

while(!q.empty()){

auto u=q.front();q.pop();

for(int i=0;i<4;i++){

int px=u.x+dir[i][0],py=u.y+dir[i][1],pt=u.t+1;

if(px<1||px>n||py<1||py>m) continue;

if(a[px][py]) continue; // 不是湖

bool flag=0;

for(int j=0;j<4;j++){ // 判断周围是否有水

// 不能方向与 i 相反，可以看一下 dir[]，小优化

if(j==(i^1)) continue;

int qx=px+dir[j][0],qy=py+dir[j][1];

if(qx<1||qx>n||qy<1||qy>m) continue;

if(a[qx][qy]){flag=1;break;}

}

if(!flag) continue;

// 若不是更优的就没必要继续往下搜了，记得更新 vis

if(vis[px][py]>pt) vis[px][py]=pt,q.push((Query){pt,px,py});

}

}

}

bool chk(int x,int y){

for(int j=0;j<4;j++){

int qx=x+dir[j][0],qy=y+dir[j][1];

if(qx<1||qx>n||qy<1||qy>m) continue;

if(a[qx][qy]||vis[qx][qy]<=tim) return true;

}

return false;

}

int main(){

read(n,m,q,r,k);

for(int i=1,ai1,bi1,ai2,bi2;i<=q;i++){

read(ai1,bi1,ai2,bi2);

for(int j=ai1;j<=ai2;j++) for(int k=bi1;k<=bi2;k++) a[j][k]=1;

}

mem(vis,0x7f);

for(int i=1;i<=r;i++){

Query tmp;read(tmp.t,tmp.x,tmp.y);

tim=tmp.t;

// 注意下面是 <tim，因为有可能有连续的相同的 t，所以等到他死透了再 pop 掉 :)

while(!que.empty()&&que.front().t<tim){

auto u=que.front();que.pop();

if(!chk(u.x,u.y)) vis[u.x][u.y]=INF;

}

bfs(tmp);

que.push((Query){tmp.t+k,tmp.x,tmp.y});

}

// t<=1e9，所以一个位置最晚在 1e9+3000*3000 个单位时间生长出树，暴力一点直接开到 2e9，注意 INF 也要开的比 2e9 大

tim=2e9;

while(!que.empty()&&que.front().t<tim){

auto u=que.front();que.pop();

if(!chk(u.x,u.y)) vis[u.x][u.y]=INF;

}

for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(!a[i][j]&&vis[i][j]<INF) cnt++;

write(cnt,'\n'),flush();

return 0;

}

好像还跑得挺快？最优解第二页？