P11394 题解

· · 题解

Problem Link

题目大意

给定 n\times m 网格，以及长度为 k 的字符串 S（字符集东南西北），初始每个格子为白色。

在第 t 个时刻，我们选取方向 S^{\infty}_t，然后取出每个格子在该方向的邻居，如果某个格子 (i,j) 连续 a_{i,j} 个时刻都取到了一个黑色的邻居，那么这个格子也染黑。

你要选择一个格子染黑，最小化充分大时间后的黑色格子数量，并且求出有多少个取到最小值的起点。

数据范围：n,m\le 800,k\le 10^5。

思路分析

首先我们要快速判定一个格子是否能染黑，取出其所有黑色邻居所在的方向，记为集合 s，那么要求就是 S^{\infty} 中存在一个长度 \ge a_{i,j} 的连续段全部由 s 中字符构成。

对每个 s 预处理出 S^{\infty} 中由 s 构成的极长连续段，可以 \mathcal O(1) 判定每个格子是否染黑。

那么暴力就是从每个点开始 bfs，但显然无法通过。

考虑利用一些已有的信息，例如从 u 出发能染黑 v，那么从 v 出发能染黑的点从 u 出发一定也会染黑。

因此可以考虑连边 u\to v，则每个点的答案就是后继个数。

先对这张图缩点，那么答案只可能是无出度的强连通分量。

可以发现如果存在一条边 u\to v，那么 u 的答案不优于 v 的答案。

因此我们取出这张图的一个内向生成森林，则答案一定来自每个根所在的强连通分量。

如果求出极大的一个内向生成森林，显然一个强连通分量内不会有两个根，因此对每个根暴力 bfs 复杂度正确。

那么问题就变成了在这张图上求出一个极大内向生成森林。

稠密图上的生成树问题可以考虑 Boruvka，在这题中，我们动态维护一个内向生成森林，然后对每个根找一条连向其他树的出边，然后以任意顺序加入这条边（只要不成环）。

很显然每轮增广后连通块数量减半，那么增广轮数是 \mathcal O(\log nm) 的。

每轮增广就从每个根开始 bfs，如果遇到一个和自己不同色的点就立即退出，那么每个点只会被同色的根 bfs 到，复杂度 \mathcal O(nm)。

时间复杂度 \mathcal O(k+nm\log nm)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=805,MAXL=2e5+5,MAXV=1e6+5,inf=1e9,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
char op[MAXL];
int n,m,q,lim[16],a[MAXN][MAXN];
int cl[MAXN][MAXN],id[MAXN][MAXN],dsu[MAXV],tot;
bool vis[MAXN][MAXN];
int ty(char c) { return c=='N'?0:(c=='S'?1:(c=='W'?2:3)); }
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>q>>n>>m;
    for(int i=1;i<=q;++i) cin>>op[i],op[i+q]=op[i];
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>a[i][j],id[i][j]=++tot;
    for(int s=1;s<16;++s) {
        for(int i=1,j=lim[s]=-1;i<=2*q;++i) if(!(s>>ty(op[i])&1)) {
            if(~j) lim[s]=max(lim[s],i-j-1); j=i;
        }
        if(lim[s]==-1) lim[s]=inf;
    }
    iota(dsu+1,dsu+tot+1,1);
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(a[i][j]) cl[i][j]=id[i][j];
    while(true) {
        memset(vis,false,sizeof(vis));
        vector <array<int,2>> E;
        int ans=inf,cnt=0;
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(cl[i][j]==id[i][j]) {
            int z=0; queue <array<int,2>> Q;
            Q.push({i,j}),vis[i][j]=true;
            auto is=[&](int x,int y){ return vis[x][y]&&cl[x][y]==cl[i][j]; };
            while(Q.size()) {
                int u=Q.front()[0],v=Q.front()[1]; Q.pop(),++z;
                for(int d:{0,1,2,3}) {
                    int x=u+dx[d],y=v+dy[d];
                    if(!a[x][y]||is(x,y)) continue;
                    int s=is(x-1,y)|is(x+1,y)<<1|is(x,y-1)<<2|is(x,y+1)<<3;
                    if(a[x][y]<=lim[s]) {
                        if(cl[x][y]==cl[i][j]) Q.push({x,y}),vis[x][y]=true;
                        else { E.push_back({cl[i][j],cl[x][y]}); goto _; }
                    }
                }
            }
            if(ans>z) ans=cnt=z;
            else if(ans==z) cnt+=z;
            _:;
        }
        if(E.empty()) return cout<<ans<<"\n"<<cnt<<"\n",0;
        for(auto e:E) if(find(e[1])!=e[0]) dsu[e[0]]=find(e[1]);
        for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(a[i][j]) cl[i][j]=find(id[i][j]);
    }
    return 0;
}