P14398 题解

人傻了写了

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$ 个很有可能少数前面的点就可达后面的点，减少重复运算。

CPP

#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;
}

文章操作

相关推荐

评论

P14398 题解