P14398 题解

dAniel_lele · 2025-11-08 20:12:43 · 题解

人傻了写了 O(\frac{n^4}{w})，其中 n 为边长，在这里是 400，由于卡常技巧比较好玩故写一篇题解。

考虑以半片三明治为单位。如果最后选取某半片三明治，那么必然要在选该半片对应的半片之前，将其所有相邻直角边上的半片三明治都取掉，因此可以连边。

不难取某半片三明治之前需要取的三明治就是其在 DAG 上可达的点，跑个 DAG 可达性即可。

然后就是卡常了！

• 直接暴力算空间很炸！我们肯定是取一个 B 然后每 B 个点一起算。
• 每次都 bfs 太慢了！我们希望 B 尽可能大，且我们可以预处理出 bfs 序。
• 每次都完整跑 n^2 个点太慢了！我们考虑按 bfs 序来每 B 个一取，这样处理完前 i\times B 个点的答案后这些点就不用再考虑了。
• 啥都 |= 太慢！由于最多只有两条出边，判断一下出边数量优化一下，同时确定 bitset 为空的点就不跑了。
• bitset 为空的点太少了！考虑把 bfs 序手法一下，每次 push_front，此时相邻 B 个很有可能少数前面的点就可达后面的点，减少重复运算。

#include <bits/stdc++.h>
//#define int long long
#define mid ((l+r)>>1)
#define lowbit(i) (i&(-i))
#define s(i,j) (((i)-1)*m+(j))
using namespace std;
const int B=5632;
int n,m;
char c[405][405];
vector<int> vc[320005];
vector<int> tr[320005];
bitset<B> bs[320005];
bool vis[320005];
int ans[320005];
int deg[320005];
int ord[320005],rpos[320005],top;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>c[i][j];
    int S=n*m;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
        {
            //s(i,j)
            if(c[i][j]=='N'){
                if(j!=1) vc[s(i,j-1)+S*(c[i][j-1]=='Z')].push_back(s(i,j));
                if(i!=n) vc[s(i+1,j)].push_back(s(i,j));
            }
            else{
                if(j!=m) vc[s(i,j+1)+S*(c[i][j+1]=='N')].push_back(s(i,j));
                if(i!=n) vc[s(i+1,j)].push_back(s(i,j));
            }
        }
        {
            //s(i,j)<<1|1
            if(c[i][j]=='N'){
                if(j!=m) vc[s(i,j+1)+S*(c[i][j+1]=='N')].push_back(s(i,j)+S);
                if(i!=1) vc[s(i-1,j)+S].push_back(s(i,j)+S);
            }
            else{
                if(j!=1) vc[s(i,j-1)+S*(c[i][j-1]=='Z')].push_back(s(i,j)+S);
                if(i!=1) vc[s(i-1,j)+S].push_back(s(i,j)+S);
            }
        }
    }
    for(int i=1;i<=(S<<1);i++) for(auto v:vc[i]) tr[v].push_back(i),deg[v]++;
    deque<int> q;
    for(int i=1;i<=(S<<1);i++) if(!deg[i]) q.push_front(i);
    while(!q.empty()){
        int f=q.front(); q.pop_front();
        ord[++top]=f;
        rpos[f]=top;
        for(auto v:vc[f]){
            deg[v]--;
            if(!deg[v]) q.push_front(v);
        }
    }
    for(int i=1;i<=(S<<1);i++) if(deg[i]) ans[i]=1e9;
    for(int l=1,r=B;l<=top;l+=B,r+=B){
        r=min(r,top);
        for(int i=min(1,l-B);i<l;i++) bs[ord[i]].reset();
        for(int i=l;i<=top;i++) vis[ord[i]]=0;
        for(int i=l;i<=top;i++){
            int f=ord[i];
            if(vis[f]){
                if(tr[f].size()==2){
                    if(!vis[tr[f][0]]) bs[f]=bs[tr[f][1]];
                    else if(!vis[tr[f][1]]) bs[f]=bs[tr[f][0]];
                    else bs[f]=bs[tr[f][0]]|bs[tr[f][1]];
                }
                else if(tr[f].size()==1) bs[f]=bs[tr[f][0]];
                ans[f]+=bs[f].count();
            }
            else bs[f].reset();
            if(l<=i&&i<=r) bs[f].set(i-l),vis[f]=1,ans[f]++;
            for(auto v:vc[f]) vis[v]|=vis[f];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int pans=min(ans[s(i,j)],ans[s(i,j)+S]);
            if(pans==1e9) cout<<-1;
            else cout<<(pans<<1);
            cout<<" \n"[j==m];
        }
    }
    return 0;
}