1 条题解

  • 0
    @ 2025-8-24 22:24:12

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Judgelight
    浮世三千,吾爱有三,日月与卿,日为朝,月为暮,卿为朝朝暮暮。

    搬运于2025-08-24 22:24:12，当前版本为作者最后更新于2024-10-14 11:52:41，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    假设没有雷为 00，有雷为 11。

    我们首先去枚举 (1,1)(1,1) 这个位置的值，我们设它是 zz，套用主元法，设第一列的所有位置 (i,1)(i,1) 的值为 ai−1a_{i-1}，第一行的所有位置 (1,i)(1,i) 的值为 bi−1b_{i-1}，忽略所有常数，以 4×44\times 4 的网格为例，我们可以得到下面这张表：

    zz b1b_1 b2b_2 b3b_3
    a1a_1 −a1−b1-a_1-b_1 −b2-b_2 a1−b3a_1-b_3
    a2a_2 −a2-a_2 00 a2a_2
    a3a_3 −a3+b1-a_3+b_1 b2b_2 a3+b3a_3+b_3

    打表可以发现每个位置只与它所在行列对应的 a,ba,b 有关，且系数绝对值不超过 11，所以我们的限制本质上是 ai±bi∈[l,r]a_i\pm b_i\in [l,r]。我们还有一个限制就是 ai,bi∈[0,1]a_i,b_i\in [0,1]。这启示我们把这个东西拿来跑 2-SAT。

    还有一个问题是关于最后一行和最后一列的限制我们是没有用到的，这个地方单独处理，算出来一些 ai,bia_i,b_i，把它们当做常数即可，时间复杂度为严格的 O(nm)O(nm)，但是带大概 88 的常数。

    代码（仅供参考）：

    #include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define mk make_pair
#define N 2009
#define Abs(x) ((x)>0?x:-x)
#define _2 0x3f3f3f3f
using namespace std;
inline char nc(){ static char buf[1000000],*p=buf,*q=buf; return p==q&&(q=(p=buf)+fread(buf,1,1000000,stdin),p==q)?EOF:*p++; } inline int rd(){ int res = 0; char c = nc(); while(c<'0'||c>'9')c=nc(); while(c<='9'&&c>='0')res=res*10+c-'0',c=nc(); return res; } char obuf[1<<21],*p3=obuf; inline void pc(char c){ p3-obuf<=(1<<20)?(*p3++=c):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=c); } inline void wt(int x){ if(x<0) pc('-'),x=-x; if(x>9) wt(x/10); pc(x%10+'0'); }
const int dx[9]={-1,-1,-1,0,0,0,1,1,1},dy[9]={-1,0,1,-1,0,1,-1,0,1};
int n,m,a[N][N];char c[N][N];
pair<int,int>p[N][N];int r[N][N];
int va[N],vb[N];
vector<int>aa[N<<1],bb[N<<1];int X[N<<1];int idx;bool del[N<<1];
struct sat2{
	#undef N
	#define N 8009
	#define M 10000009
	#define g(a,b) (a+(b?0:n))
	int n,m;bitset<N>e[N];
	inline void add(int u,int v){e[u][v]=1;}
	int stk[N],top,instk[N],dfn[N],low[N],timestamps,id[N],scnt;
	void tarjan(int u){
		stk[++top]=u,instk[u]=1,dfn[u]=low[u]=++timestamps;
		for(int v=e[u]._Find_first();v!=e[u].size();v=e[u]._Find_next(v)){
			if(!dfn[v]){
				tarjan(v),low[u]=min(low[u],low[v]);
			}
			else if(instk[v])low[u]=min(low[u],dfn[v]);
		}
		if(dfn[u]==low[u]){
			int v;scnt++;
			do{
				v=stk[top--],instk[v]=0;
				id[v]=scnt;
			}
			while(v!=u);
		}
	}
	inline void add(int p,int a,int q,int b){add(g(p,a),g(q,b));}
	int c[N];
	bool solve(int n){
		for(int i=1;i<=(n<<1);i++)if(!dfn[i])tarjan(i);
		for(int i=1;i<=n;i++)if(id[g(i,0)]==id[g(i,1)])return 0;
		for(int i=1;i<=n;i++)c[i]=id[g(i,1)]<id[g(i,0)];
		return 1;
	}
	void clean(){
		for(int i=1;i<=(n<<1);i++)e[i].reset();
		memset(stk,0,sizeof(stk)),top=0,memset(instk,0,sizeof(instk)),memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),timestamps=0,memset(id,0,sizeof(id)),scnt=0;
	}
}T;
signed main(){
	//freopen("ex_minesweeper5.in","r",stdin);
	//freopen("Misaka.txt","w",stdout);
	n=rd(),m=rd();
	for(int i=1;i<=n;i++)va[i]=_2;for(int i=1;i<=m;i++)vb[i]=_2;
	for(int i=1;i<=n;i++){
		char ch=nc();
		while(ch<'0'||ch>'9')ch=nc();
		int nw=0;
		while(ch>='0'&&ch<='9'){
			c[i][++nw]=ch,ch=nc();
		}
		for(int j=1;j<=m;j++)a[i][j]=c[i][j]-'0';
	}
	r[1][1]=0;
	for(int i=2;i<=n;i++)p[i][1]=mk(i-1,0);
	for(int i=2;i<=m;i++)p[1][i]=mk(0,i-1);
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			int x=a[i-1][j-1];
			for(int t=0;t<9;t++){
				int ii=i-1+dx[t],jj=j-1+dy[t];
				if(ii<=0||jj<=0||ii>n||jj>m||(ii==i&&jj==j))continue;
				p[i][j].first-=p[ii][jj].first,p[i][j].second-=p[ii][jj].second;
				x-=r[ii][jj];
			}
			r[i][j]=x;
		}
	}
	for(int i=1;i<=n;i++){
		map<int,int>ma,mb;idx++;X[idx]=a[i][m];
		for(int t=0;t<9;t++){
			int ii=i+dx[t],jj=m+dy[t];
			if(ii<=0||jj<=0||ii>n||jj>m)continue;
			ma[Abs(p[ii][jj].first)]+=p[ii][jj].first,mb[Abs(p[ii][jj].second)]+=p[ii][jj].second;
			X[idx]-=r[ii][jj];
		}
		for(auto x:ma){
			if(x.second!=0)aa[idx].eb(x.second);
		}
		for(auto x:mb){
			if(x.second!=0)bb[idx].eb(x.second);
		}
	}
	for(int i=1;i<=m;i++){
		map<int,int>ma,mb;idx++;X[idx]=a[n][i];
		for(int t=0;t<9;t++){
			int ii=n+dx[t],jj=i+dy[t];
			if(ii<=0||jj<=0||ii>n||jj>m)continue;
			ma[Abs(p[ii][jj].first)]+=p[ii][jj].first,mb[Abs(p[ii][jj].second)]+=p[ii][jj].second;
			X[idx]-=r[ii][jj];
		}
		for(auto x:ma){
			if(x.second!=0)aa[idx].eb(x.second);
		}
		for(auto x:mb){
			if(x.second!=0)bb[idx].eb(x.second);
		}
	}
	for(int t=1;;t++){
		bool flag=0;
		for(int i=1;i<=idx;i++){
			if(del[i])continue;
			vector<int>a,b;int Y=X[i];
			for(auto x:aa[i]){
				if(va[Abs(x)]!=_2)Y-=(x/Abs(x))*va[Abs(x)];
				else a.eb(x);
			}
			for(auto x:bb[i]){
				if(vb[Abs(x)]!=_2)Y-=(x/(Abs(x)))*vb[Abs(x)];
				else b.eb(x);
			}
			if(a.size()==1&&b.size()==0){
				flag=1;
				del[i]=1;va[Abs(a[0])]=(a[0]/Abs(a[0]))*Y;
				aa[i]=a,bb[i]=b,X[i]=Y;
				continue;
			}
			if(b.size()==1&&a.size()==0){
				flag=1;
				del[i]=1;vb[Abs(b[0])]=(b[0]/Abs(b[0]))*Y;
				aa[i]=a,bb[i]=b,X[i]=Y;
				continue;
			}
			aa[i]=a,bb[i]=b,X[i]=Y;
		}
		if(!flag)break;
	}
	bool flag=0;
	for(int i=1;i<n;i++)if(va[i]!=_2&&va[i]!=0&&va[i]!=1){flag=1;break;}
	for(int i=1;i<m;i++)if(vb[i]!=_2&&vb[i]!=0&&vb[i]!=1){flag=1;break;}
	if(!flag){
		T.n=n+m-2;
		for(int i=1;i<n;i++)if(va[i]!=_2)T.add(i,va[i]^1,i,va[i]);
		for(int i=1;i<m;i++)if(vb[i]!=_2)T.add(i+n-1,vb[i]^1,i,vb[i]);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(p[i][j].first!=0&&va[Abs(p[i][j].first)]!=_2){
					r[i][j]+=(p[i][j].first/Abs(p[i][j].first))*va[Abs(p[i][j].first)],p[i][j].first=0;
				}
				if(p[i][j].second!=0&&vb[Abs(p[i][j].second)]!=_2){
					r[i][j]+=(p[i][j].second/Abs(p[i][j].second))*vb[Abs(p[i][j].second)],p[i][j].second=0;
				}
				if(p[i][j].first==0&&p[i][j].second==0)continue;
				if(p[i][j].second==0){
					int L=0-r[i][j],R=1-r[i][j];if(p[i][j].first<0)L=-L,R=-R,swap(L,R);
					int x=Abs(p[i][j].first);
					if(L==1)T.add(x,0,x,1);
					if(R==0)T.add(x,1,x,0);
				}
				else if(p[i][j].first==0){
					int L=0-r[i][j],R=1-r[i][j];if(p[i][j].second<0)L=-L,R=-R,swap(L,R);
					int x=Abs(p[i][j].second)+n-1;
					if(L==1)T.add(x,0,x,1);
					if(R==0)T.add(x,1,x,0);
				}
				else{
					int x=Abs(p[i][j].first),y=Abs(p[i][j].second)+n-1;int L=0-r[i][j],R=1-r[i][j];
					if(p[i][j].first>0&&p[i][j].second>0){
						if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,x+y!=0
						if(1<L||1>R)T.add(x,0,y,0);//x=0,y!=1,x+y!=1
						if(1<L||1>R)T.add(x,1,y,1);//x=1,y!=0,x+y!=1
						if(2<L||2>R)T.add(x,1,y,0);//x=1,y!=1,x+y!=2
						//
						if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,x+y!=0
						if(1<L||1>R)T.add(y,0,x,0);//y=0,x!=1,x+y!=1
						if(1<L||1>R)T.add(y,1,x,1);//y=1,x!=0,x+y!=1
						if(2<L||2>R)T.add(y,1,x,0);//y=1,x!=1,x+y!=2
					}
					else if(p[i][j].first>0&&p[i][j].second<0){
						if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,x-y!=0
						if(-1<L||-1>R)T.add(x,0,y,0);//x=0,y!=1,x-y!=-1
						if(1<L||1>R)T.add(x,1,y,1);//x=1,y!=0,x-y!=1
						if(0<L||0>R)T.add(x,1,y,0);//x=1,y!=1,x-y!=0
						//
						if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,x-y!=0
						if(1<L||1>R)T.add(y,0,x,0);//y=0,x!=1,x-y!=1
						if(-1<L||-1>R)T.add(y,1,x,1);//y=1,x!=0,x-y!=-1
						if(0<L||0>R)T.add(y,1,x,0);//y=1,x!=1,x-y!=0
					}
					else if(p[i][j].first<0&&p[i][j].second>0){
						if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,y-x!=0
						if(-1<L||-1>R)T.add(y,0,x,0);//y=0,x!=1,y-x!=-1
						if(1<L||1>R)T.add(y,1,x,1);//y=1,x!=0,y-x!=1
						if(0<L||0>R)T.add(y,1,x,0);//y=1,x!=1,y-x!=0
						//
						if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,y-x!=0
						if(1<L||1>R)T.add(x,0,y,0);//x=0,y!=1,y-x!=1
						if(-1<L||-1>R)T.add(x,1,y,1);//x=1,y!=0,y-x!=-1
						if(0<L||0>R)T.add(x,1,y,0);//x=1,y!=1,y-x!=0
					}
					else{
						if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,-x-y!=0
						if(-1<L||-1>R)T.add(x,0,y,0);//x=0,y!=1,-x-y!=-1
						if(-1<L||-1>R)T.add(x,1,y,1);//x=1,y!=0,-x-y!=-1
						if(-2<L||-2>R)T.add(x,1,y,0);//x=1,y!=1,-x-y!=-2
						//
						if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,-x-y!=0
						if(-1<L||-1>R)T.add(y,0,x,0);//y=0,x!=1,-x-y!=-1
						if(-1<L||-1>R)T.add(y,1,x,1);//y=1,x!=0,-x-y!=-1
						if(-2<L||-2>R)T.add(y,1,x,0);//y=1,x!=1,-x-y!=-2
					}
				}
			}
		}
		if(T.solve(n+m-2)){
			for(int i=1;i<n;i++)va[i]=T.c[i];
			for(int i=1;i<m;i++)vb[i]=T.c[i+n-1];
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++){
					int x=r[i][j];
					if(p[i][j].first)x+=va[Abs(p[i][j].first)]*(p[i][j].first/Abs(p[i][j].first));
					if(p[i][j].second)x+=vb[Abs(p[i][j].second)]*(p[i][j].second/(Abs(p[i][j].second)));
					x==0?pc('0'):pc('1');
				}
				pc('\n');
			}
			fwrite(obuf,p3-obuf,1,stdout);
			return 0;
		}
	}
	/////////////////////////////////////////////////////////////////
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)p[i][j]=mk(0,0);for(int i=1;i<=n+m;i++)aa[i].clear(),bb[i].clear(),X[i]=0,del[i]=0;idx=0;
	T.clean();
	memset(r,0,sizeof(r)),memset(va,0,sizeof(va)),memset(vb,0,sizeof(vb));
	for(int i=1;i<=n;i++)va[i]=_2;for(int i=1;i<=m;i++)vb[i]=_2;
	r[1][1]=1;
	for(int i=2;i<=n;i++)p[i][1]=mk(i-1,0);
	for(int i=2;i<=m;i++)p[1][i]=mk(0,i-1);
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			int x=a[i-1][j-1];
			for(int t=0;t<9;t++){
				int ii=i-1+dx[t],jj=j-1+dy[t];
				if(ii<=0||jj<=0||ii>n||jj>m||(ii==i&&jj==j))continue;
				p[i][j].first-=p[ii][jj].first,p[i][j].second-=p[ii][jj].second;
				x-=r[ii][jj];
			}
			r[i][j]=x;
		}
	}
	for(int i=1;i<=n;i++){
		map<int,int>ma,mb;idx++;X[idx]=a[i][m];
		for(int t=0;t<9;t++){
			int ii=i+dx[t],jj=m+dy[t];
			if(ii<=0||jj<=0||ii>n||jj>m)continue;
			ma[Abs(p[ii][jj].first)]+=p[ii][jj].first,mb[Abs(p[ii][jj].second)]+=p[ii][jj].second;
			X[idx]-=r[ii][jj];
		}
		for(auto x:ma){
			if(x.second!=0)aa[idx].eb(x.second);
		}
		for(auto x:mb){
			if(x.second!=0)bb[idx].eb(x.second);
		}
	}
	for(int i=1;i<=m;i++){
		map<int,int>ma,mb;idx++;X[idx]=a[n][i];
		for(int t=0;t<9;t++){
			int ii=n+dx[t],jj=i+dy[t];
			if(ii<=0||jj<=0||ii>n||jj>m)continue;
			ma[Abs(p[ii][jj].first)]+=p[ii][jj].first,mb[Abs(p[ii][jj].second)]+=p[ii][jj].second;
			X[idx]-=r[ii][jj];
		}
		for(auto x:ma){
			if(x.second!=0)aa[idx].eb(x.second);
		}
		for(auto x:mb){
			if(x.second!=0)bb[idx].eb(x.second);
		}
	}
	for(int t=1;;t++){
		bool flag=0;
		for(int i=1;i<=idx;i++){
			if(del[i])continue;
			vector<int>a,b;int Y=X[i];
			for(auto x:aa[i]){
				if(va[Abs(x)]!=_2)Y-=(x/Abs(x))*va[Abs(x)];
				else a.eb(x);
			}
			for(auto x:bb[i]){
				if(vb[Abs(x)]!=_2)Y-=(x/(Abs(x)))*vb[Abs(x)];
				else b.eb(x);
			}
			if(a.size()==1&&b.size()==0){
				flag=1;
				del[i]=1;va[Abs(a[0])]=(a[0]/Abs(a[0]))*Y;
				aa[i]=a,bb[i]=b,X[i]=Y;
				continue;
			}
			if(b.size()==1&&a.size()==0){
				flag=1;
				del[i]=1;vb[Abs(b[0])]=(b[0]/Abs(b[0]))*Y;
				aa[i]=a,bb[i]=b,X[i]=Y;
				continue;
			}
			aa[i]=a,bb[i]=b,X[i]=Y;
		}
		if(!flag)break;
	}
	T.n=n+m-2;
	for(int i=1;i<n;i++)if(va[i]!=_2)T.add(i,va[i]^1,i,va[i]);
	for(int i=1;i<m;i++)if(vb[i]!=_2)T.add(i+n-1,vb[i]^1,i,vb[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(p[i][j].first!=0&&va[Abs(p[i][j].first)]!=_2){
				r[i][j]+=(p[i][j].first/Abs(p[i][j].first))*va[Abs(p[i][j].first)],p[i][j].first=0;
			}
			if(p[i][j].second!=0&&vb[Abs(p[i][j].second)]!=_2){
				r[i][j]+=(p[i][j].second/Abs(p[i][j].second))*vb[Abs(p[i][j].second)],p[i][j].second=0;
			}
			if(p[i][j].first==0&&p[i][j].second==0)continue;
			if(p[i][j].second==0){
				int L=0-r[i][j],R=1-r[i][j];if(p[i][j].first<0)L=-L,R=-R,swap(L,R);
				int x=Abs(p[i][j].first);
				if(L==1)T.add(x,0,x,1);
				if(R==0)T.add(x,1,x,0);
			}
			else if(p[i][j].first==0){
				int L=0-r[i][j],R=1-r[i][j];if(p[i][j].second<0)L=-L,R=-R,swap(L,R);
				int x=Abs(p[i][j].second)+n-1;
				if(L==1)T.add(x,0,x,1);
				if(R==0)T.add(x,1,x,0);
			}
			else{
				int x=Abs(p[i][j].first),y=Abs(p[i][j].second)+n-1;int L=0-r[i][j],R=1-r[i][j];
				if(p[i][j].first>0&&p[i][j].second>0){
					if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,x+y!=0
					if(1<L||1>R)T.add(x,0,y,0);//x=0,y!=1,x+y!=1
					if(1<L||1>R)T.add(x,1,y,1);//x=1,y!=0,x+y!=1
					if(2<L||2>R)T.add(x,1,y,0);//x=1,y!=1,x+y!=2
					//
					if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,x+y!=0
					if(1<L||1>R)T.add(y,0,x,0);//y=0,x!=1,x+y!=1
					if(1<L||1>R)T.add(y,1,x,1);//y=1,x!=0,x+y!=1
					if(2<L||2>R)T.add(y,1,x,0);//y=1,x!=1,x+y!=2
				}
				else if(p[i][j].first>0&&p[i][j].second<0){
					if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,x-y!=0
					if(-1<L||-1>R)T.add(x,0,y,0);//x=0,y!=1,x-y!=-1
					if(1<L||1>R)T.add(x,1,y,1);//x=1,y!=0,x-y!=1
					if(0<L||0>R)T.add(x,1,y,0);//x=1,y!=1,x-y!=0
					//
					if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,x-y!=0
					if(1<L||1>R)T.add(y,0,x,0);//y=0,x!=1,x-y!=1
					if(-1<L||-1>R)T.add(y,1,x,1);//y=1,x!=0,x-y!=-1
					if(0<L||0>R)T.add(y,1,x,0);//y=1,x!=1,x-y!=0
				}
				else if(p[i][j].first<0&&p[i][j].second>0){
					if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,y-x!=0
					if(-1<L||-1>R)T.add(y,0,x,0);//y=0,x!=1,y-x!=-1
					if(1<L||1>R)T.add(y,1,x,1);//y=1,x!=0,y-x!=1
					if(0<L||0>R)T.add(y,1,x,0);//y=1,x!=1,y-x!=0
					//
					if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,y-x!=0
					if(1<L||1>R)T.add(x,0,y,0);//x=0,y!=1,y-x!=1
					if(-1<L||-1>R)T.add(x,1,y,1);//x=1,y!=0,y-x!=-1
					if(0<L||0>R)T.add(x,1,y,0);//x=1,y!=1,y-x!=0
				}
				else{
					if(0<L||0>R)T.add(x,0,y,1);//x=0,y!=0,-x-y!=0
					if(-1<L||-1>R)T.add(x,0,y,0);//x=0,y!=1,-x-y!=-1
					if(-1<L||-1>R)T.add(x,1,y,1);//x=1,y!=0,-x-y!=-1
					if(-2<L||-2>R)T.add(x,1,y,0);//x=1,y!=1,-x-y!=-2
					//
					if(0<L||0>R)T.add(y,0,x,1);//y=0,x!=0,-x-y!=0
					if(-1<L||-1>R)T.add(y,0,x,0);//y=0,x!=1,-x-y!=-1
					if(-1<L||-1>R)T.add(y,1,x,1);//y=1,x!=0,-x-y!=-1
					if(-2<L||-2>R)T.add(y,1,x,0);//y=1,x!=1,-x-y!=-2
				}
			}
		}
	}
	if(T.solve(n+m-2)){
		for(int i=1;i<n;i++)va[i]=T.c[i];
		for(int i=1;i<m;i++)vb[i]=T.c[i+n-1];
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int x=r[i][j];
				if(p[i][j].first)x+=va[Abs(p[i][j].first)]*(p[i][j].first/Abs(p[i][j].first));
				if(p[i][j].second)x+=vb[Abs(p[i][j].second)]*(p[i][j].second/(Abs(p[i][j].second)));
				x==0?pc('0'):pc('1');
			}
			pc('\n');
		}
		fwrite(obuf,p3-obuf,1,stdout);
		return 0;
	}
	return 0;
}
    • 1

    [BalticOI 2010] Mines (Day2)

    信息

    ID
    5820
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 23ms