SS241009B. 贪吃蛇（snake）
SS241009B. 贪吃蛇（snake）
题意
给你一个 \(n \times m\) 的矩阵，满足 \(n \times m \le 10^6\)。每个点有一个权值 \(a_{i,j}\)。从一个点出发，能量值是这个点的点权，然后可以走到四周比它能量小的结点，吃掉它并合并能量。问从每个位置出发，能不能吃完整个地图。
思路
首先显然的贪心是我们每次吃掉最小的可以吃的点，然后可以做暴力了。
经过敏锐的观察显然我没有可以发现，我扩展到的所有比我大的点，如果有一个大点可以吃完所有，那么我也可以吃完所有。
题解说加上一些面向数据的剪枝可以水过去。
然后考虑对于每个点，向所有点权小于等于它的点权的点扩展，直到周围一圈的点权都比它大，这样形成一个关于这个点的连通块。然后再判断现在的它在吃掉连通块内的所有点之后更新能量后能否吃掉周围最小的点。
这个看起来就比较有前途，吧。考虑按照权值顺序枚举每一个点，然后充分利用之前的信息，以此降低复杂度。
按照权值从小到大枚举权值 \(v\)，对于 \(a_i=v\)（这里把坐标的两维压成一维）,可以继承四周比它小的点的已经处理了的连通块，合并连通块。
这样的连通块满足每个连通块内最大值 \(=v\)。也就是说连通块内每一个点权都 \(\le v\)。维护连通块的权值和，如果连通块权值和小于周围最小的点，那么整个连通块所有点的答案都是 \(0\)。
对于吃掉全部的连通块，它是由若干个权值最大的点，合并若干个连通块得到的一个连通块，对于答案没有钦定为 \(0\) 的点，叫做我，关于我的连通块的周围的最小点权的点到时候一定会把我合并，然后一直合并，直到合并成吃掉全部，这一路上没有因周围过大而导致连通块清零的情况，因此我出发可以吃掉全部，我的答案是 \(1\)。因此，最后所有没有被清零的点的答案都是 \(1\)。
连通块合并用并查集维护，同时维护连通块权值和。判断连通块周围的最小点能否到达，线性做法是在枚举到外面那个最小的点的时候，把连通块称作我，它就会把我合并，然后这时候判断它和我的大小关系，如果我比较小就把我清零。清零连通块就钦定每个连通块是哪个点的时候合并起来的，即每个连通块是关于哪个点的连通块，以那个点作为连通块的祖先，然后把这些祖先按照合并关系建成树，在树上打标记，最后遍历树即可。
时间复杂度 \(O(n \log n)\)。
code
代码还是不难写的。
#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int N=1e6+7;
typedef long long ll;
int n,m;
ll a[N];
int b[N];
const int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int fa[N];
ll siz[N];
int id[N];
bool cmp (int x, int y) { return a[x] < a[y] ; }
vector<int> son[N];
bool tag[N];
int findfa(int x) {
if(x==fa[x]) return x;
return fa[x]=findfa(fa[x]);
}
void merge(int x, int y) {
int fx=findfa(x), fy=findfa(y);
if(fx==fy) return;
son[fx].push_back(fy);
if(siz[fy]<a[b[x]]) tag[fy]=1;
siz[fx]+=siz[fy], fa[fy]=fx;
}
bool ans[N];
void dfs(int x) {
if(tag[x]) return;
ans[b[x]]=1;
for(int v:son[x]) { dfs(v); }
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#else
freopen("snake.in","r",stdin);
freopen("snake.out","w",stdout);
#endif
sf("%d%d",&n,&m);
rep(i,0,n*m-1) {
sf("%lld",&a[i]);
b[i]=i;
}
sort(b,b+n*m,cmp);
rep(i,0,n*m-1) id[b[i]]=i;
rep(i,0,n*m-1) {
fa[i]=i; siz[i]=a[b[i]];
int x=b[i]/m,y=b[i]%m;
rep(j,0,3) {
int xx=x+dir[j][0],yy=y+dir[j][1];
if(xx>=0&&xx<n&&yy>=0&&yy<m) if(id[xx*m+yy]<i) merge(i,id[xx*m+yy]);
}
}
dfs(n*m-1);
rep(x,0,n-1) {
rep(y,0,m-1) pf("%d ",ans[x*m+y]==1?1:0);
pf("\n");
}
}