专栏文章

题解：P3208 [HNOI2010] 矩阵

ddiqiuyi奶龙
P3208题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio8zbis
此快照首次捕获于
2025/12/02 15:19
3 个月前
此快照最后确认于
2025/12/02 15:19
3 个月前
查看原文
不太懂爆搜为啥能过，所以这是一篇 2-SAT 题解。
设和矩阵为 ss，原矩阵为 aa。考虑用 a1,xa_{1,x} 和 ax,1a_{x,1} 表示 ai,ja_{i,j}。有 ai,j=si,j−ai−1,j−ai,j−1−ai−1,j−1a_{i,j}=s_{i,j}-a_{i-1,j}-a_{i,j-1}-a_{i-1,j-1}。它的常数项 bi,jb_{i,j} 可以直接递推出来，剩下的部分是一个格路计数状物。对于没有拐弯的路线，它的权值是 (−1)len(-1)^{len}；对于有拐弯的路线，把第一次拐弯换成走斜线刚好可以抵消。这个双射只有从 a1,1a_{1,1} 出发右下交替走到 amin⁡(i,j),min⁡(i,j)a_{\min(i,j),\min(i,j)} 然后再走到 ai,ja_{i,j} 的路径会漏掉。所以 ai,j=bi,j+(−1)i+1a1,j+(−1)j+1ai,1+(−1)i+j+1a1,1a_{i,j}=b_{i,j}+(-1)^{i+1}a_{1,j}+(-1)^{j+1}a_{i,1}+(-1)^{i+j+1}a_{1,1}。
所以我们可以枚举 a1,1a_{1,1}，然后就是形如 a1,i+aj,1∈[l,r]a_{1,i}+a_{j,1}\in[l,r] 的限制。把 a1,xa_{1,x} 和 ax,1a_{x,1} 拆成 pp 个点后这些限制可以用 2-SAT 来刻画。令 V=np,E=n2pV=np,E=n^2p，需要跑 pp 次 2-SAT，11 次最小字典序，复杂度为 O(pE+VE)O(pE+VE)，无法通过。
但是可以使用 bitset 来求最小字典序 2-SAT，方法大致是缩点后维护每个点可达的点集，然后就可以容易判断这个点能否取 1。时间复杂度为变为 O(pE+VEw)O(pE+\dfrac{VE}w)，可以通过。
下面这份代码的复杂度是 O(pE+VEw+V2)O(pE+\dfrac{VE}w+V^2) 的，因为我懒。
CPP
#include <bits/stdc++.h>
using namespace std;
int n,m,p,tot,b[205][205],pos[8005],top,cnt,stk[8005],s[205][205],a[205][205];
bitset<8005> to[8005],e[8005],fe[8005],g[2][8005],vis,cl; 
vector<int> cc[8005];
int id(int i,int j,int v,int op){
	return 2*((!i?j:i+m-1)-1)*p+(v-1)*2+op+1;
}
void Add(int u,int v){
//	cout<<"u,v:"<<u<<' '<<v<<'\n';
	e[u][v]=fe[v][u]=1;
}
void dfs(int x){
	vis[x]=0;
	for(int i=(vis&e[x])._Find_first();i<=tot;i=(vis&e[x])._Find_first())
		dfs(i);
	stk[++top]=x;
}
void dfs2(int x){
	vis[x]=0,pos[x]=cnt,cc[cnt].push_back(x);
	for(int i=(vis&fe[x])._Find_first();i<=tot;i=(vis&fe[x])._Find_first())
		dfs2(i);
}
int fd(int x){
	return x&1?x+1:x-1;
}
void col(int x,int v){
	if(!vis[x]) return ;
	cl[x]=v,vis[x]=0;
	for(int u:cc[x])
		if(vis[pos[fd(u)]])
			col(pos[fd(u)],v^1);
	for(int i=(vis&g[v][x])._Find_first();i<=cnt;i=(vis&g[v][x])._Find_first())
		col(i,v);
}
void solve(int x){
	for(int i=1;i<=tot;i++) e[i].reset(),fe[i].reset(),cc[i].clear();
	for(int i=1;i<m;i++){
		for(int j=1;j<p;j++)
			Add(id(0,i,j,0),id(0,i,j+1,0)),Add(id(0,i,j+1,1),id(0,i,j,1));
		Add(id(0,i,p,1),id(0,i,p,0));
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<p;j++)
			Add(id(i,0,j,0),id(i,0,j+1,0)),Add(id(i,0,j+1,1),id(i,0,j,1));
		Add(id(i,0,p,1),id(i,0,p,0));
	}
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++){
			b[i][j]=s[i][j]+(i+j&1?x:-x);
			int l=1-b[i][j],r=p-b[i][j];
			if(i&1) l=-l,r=-r,swap(l,r);
//			cout<<"l,r:"<<l<<" "<<r<<'\n';
			if(i+j&1){
				if(l>p-1||r<1-p) return ;
				for(int k=1;k<=p;k++){
					int v=k-l;
					if(v>=1&&v<=p) Add(id(0,j,k,0),id(i,0,v,0));
					else if(v<1) Add(id(0,j,k,0),id(0,j,k,1));
					v=k-r;
					if(v>=1&&v<=p) Add(id(0,j,k,1),id(i,0,v,1));
					else if(v>p) Add(id(0,j,k,1),id(0,j,k,0));
				}
				l=-l,r=-r,swap(l,r);
				if(l>p-1||r<1-p) return ;
				for(int k=1;k<=p;k++){
					int v=k-l;
					if(v>=1&&v<=p) Add(id(i,0,k,0),id(0,j,v,0));
					else if(v<1) Add(id(i,0,k,0),id(i,0,k,1));
					v=k-r;
					if(v>=1&&v<=p) Add(id(i,0,k,1),id(0,j,v,1));
					else if(v>p) Add(id(i,0,k,1),id(i,0,k,0));
				}
			}
			else{
				if(l>2*p||r<2) return ;
				for(int k=1;k<=p;k++){
					int v=l-k-1;
					if(v>=1&&v<=p) Add(id(0,j,k,0),id(i,0,v,1)),Add(id(i,0,k,0),id(0,j,v,1));
					else if(v>p) Add(id(0,j,k,0),id(0,j,k,1)),Add(id(i,0,k,0),id(i,0,k,1));
					v=r-k-1;
					if(v>=1&&v<=p) Add(id(0,j,k,1),id(i,0,v,0)),Add(id(i,0,k,1),id(0,j,v,0));
					else if(v<1) Add(id(0,j,k,1),id(0,j,k,0)),Add(id(i,0,k,1),id(i,0,k,0));
				}
			}
		}
	vis.set(),top=0;
	for(int i=1;i<=tot;i++)
		if(vis[i])
			dfs(i);
	cnt=0;vis.set();
	for(;top;top--)
		if(vis[stk[top]])
			cnt++,dfs2(stk[top]);
	for(int i=1;i<=tot;i+=2)
		if(pos[i]==pos[i+1])
			return ;
//	cout<<cnt<<' '<<tot<<'\n';
	for(int i=1;i<=cnt;i++) g[0][i][i]=g[1][i][i]=to[i][i]=1;
	for(int i=1;i<=tot;i++)
		for(int j=1;j<=tot;j++)
			if(e[i][j])
				g[0][pos[i]][pos[j]]=g[1][pos[j]][pos[i]]=1;
	for(int i=cnt;i;i--)
		for(int j=i;j<=cnt;j++)
			if(g[0][i][j])
				to[i]|=to[j];
	vis.set();
	for(int i=1;i<tot;i+=2)
		if(vis[pos[i]]&&vis[pos[i+1]]){
			if((cl&to[pos[i]]).any()||to[pos[i]][pos[i+1]]) col(pos[i+1],0);
			else col(pos[i],0);
	 	}
	a[0][0]=x;
	for(int i=1;i<m;i++)
		for(int j=1;j<=p;j++)
			if(!cl[pos[id(0,i,j,0)]]){
				a[0][i]=j;
				break;
			}
	for(int i=1;i<n;i++)
		for(int j=1;j<=p;j++)
			if(!cl[pos[id(i,0,j,0)]]){
				a[i][0]=j;
				break;
			}
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++)
			a[i][j]=(i&1?-a[0][j]:a[0][j])+(j&1?-a[i][0]:a[i][0])+b[i][j];
	for(int i=0;i<n;cout<<'\n',i++)
		for(int j=0;j<m;j++)
			cout<<a[i][j]-1<<" ";
	exit(0);
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>p,tot=(n+m-2)*2*p;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			cin>>s[i][j];
	for(int i=1;i<n;i++)
		for(int j=1;j<m;j++)
			s[i][j]+=4,s[i][j]=s[i][j]-s[i-1][j]-s[i-1][j-1]-s[i][j-1];
	for(int i=1;i<=p;i++)
		solve(i);
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...