表示今天一發(fā)A了這題拿了rk3...是個sb構(gòu)造...

考慮除了\(n=1/m=1\)的情況，最小次數(shù)\(ans\)不會\(>3\)。

對于\(n=1/m=1\)，暴力即可。

然后考慮\(ans=0\)，只有在圖中沒有\(1\)時成立。

對于\(ans=1\)，圖中的\(1\)是一個四聯(lián)通塊

對于\(ans=2\)，加入圖中的某個\(0\)的四聯(lián)通塊后所有的\(1\)是一個四聯(lián)通塊。

對于其他的情況，若\(\max(n,m)<3\)，顯然只有\(n=m=2\)，枚舉\(16\)種情況發(fā)現(xiàn)\(ans\leq 2\)。

所以考慮有\(\max(n,m)\geq 3\)，此時一定可以構(gòu)造出\(ans=3\)的合法方案。構(gòu)造方式如下：

• 不妨設(shè)\(n\leq m\)，則\(m\geq3\)。
• 兩個矩陣為+，一個矩陣為-。
• 將第一個矩陣的第一列和奇數(shù)行的第二列到第\(m-1\)列設(shè)為\(1\)。
• 將第二個矩陣的第\(m\)列和偶數(shù)行的第二列到第\(m-1\)列設(shè)為\(1\)。
• 將兩個矩陣第二列到第\(m-1\)列在目標矩陣中的對應(yīng)位置為\(1\)的位置設(shè)為\(1\)（此時一定滿足四聯(lián)通性質(zhì)）。
• 將第三個矩陣的第二列到第\(m-1\)列設(shè)為\(1\)，第一列和第\(m\)列在目標矩陣中的對應(yīng)位置為\(0\)的位置設(shè)為\(1\)。

此時一定可以構(gòu)造出合法的方案，\(ans=3\)。

槽點：這題\(n,m\leq500\)挺垃圾的，為什么不開\(n,m\leq5000\)（雖說得稍微改一下實現(xiàn)）。

放代碼：代碼里面有些重復(fù)的東西是復(fù)制出來的所以看起來可能會有點丑...

#include<bits/stdc++.h>using namespace std;const int N=502,fx[2][4]={{0,0,1,-1},{1,-1,0,0}};int n,m;char s[N][N],t[N][N],r[N][N],q[N][N];int vis[N][N],cnt[2];bool check0(){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='1'){return 0;}}}return 1; }void solve0(){printf("0\n"); }void dfs1(int u,int v){if(vis[u][v]){return;}vis[u][v]=1;for(int i=0,tx,ty;i<4;i++){tx=u+fx[0][i];ty=v+fx[1][i];if(tx<1||ty<1||tx>n||ty>m){continue;}if(s[tx][ty]=='1'&&!vis[tx][ty]){dfs1(tx,ty);}} }bool check1(){memset(vis,0,sizeof vis);bool flag=1;for(int i=1;i<=n;i++){if(!flag){break;}for(int j=1;j<=m;j++){if(s[i][j]=='1'){dfs1(i,j);flag=0;break;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='1'){if(!vis[i][j]){return 0;}}}}return 1; }void solve1(){printf("1\n+\n");for(int i=1;i<=n;i++){printf("%s\n",s[i]+1);} }set<int>st;void dfs2(int u,int v,int w){if(vis[u][v]){return;}vis[u][v]=w;for(int i=0,tx,ty;i<4;i++){tx=u+fx[0][i];ty=v+fx[1][i];if(tx<1||ty<1||tx>n||ty>m){continue;}if(s[tx][ty]=='0'&&!vis[tx][ty]){dfs2(tx,ty,w);}else if(s[tx][ty]=='1'){st.insert(vis[tx][ty]);}} }void dfs21(int u,int v,int w){if(vis[u][v]){return;}vis[u][v]=w;for(int i=0,tx,ty;i<4;i++){tx=u+fx[0][i];ty=v+fx[1][i];if(tx<1||ty<1||tx>n||ty>m){continue;}if(s[tx][ty]=='1'&&!vis[tx][ty]){dfs21(tx,ty,w);}} }bool check2(){memset(vis,0,sizeof vis);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='1'&&!vis[i][j]){dfs21(i,j,++cnt[1]);}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(s[i][j]=='0'&&!vis[i][j]){st.clear();dfs2(i,j,++cnt[0]);if((int)st.size()==cnt[1]){return 1;}}}}return 0; }void solve2(){printf("2\n");for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){t[i][j]=s[i][j];q[i][j]='0';if(s[i][j]=='0'&&vis[i][j]==cnt[0]){t[i][j]='1';q[i][j]='1';}}}printf("+\n");for(int i=1;i<=n;i++){printf("%s\n",t[i]+1);}printf("-\n");for(int i=1;i<=n;i++){printf("%s\n",q[i]+1);} }int lb[N],rb[N];void solven1(){memset(vis,0,sizeof vis);memset(cnt,0,sizeof cnt);memset(lb,0x3f,sizeof lb);for(int i=1;i<=m;i++){if(s[1][i]=='1'){if(vis[1][i]){continue;}dfs21(1,i,++cnt[1]);}}for(int i=1;i<=m;i++){if(vis[1][i]){lb[vis[1][i]]=min(lb[vis[1][i]],i);rb[vis[1][i]]=max(rb[vis[1][i]],i);}}int ans=cnt[1],lmt,ll=1,rr=cnt[1];printf("%d\n",ans);if(cnt[1]&1){lmt=ans>>1;for(int i=1;i<=lmt;i++){printf("+\n");for(int j=1;j<=m;j++){t[1][j]='0';}for(int j=lb[ll];j<=rb[rr];j++){t[1][j]='1';}printf("%s\n",t[1]+1);printf("-\n");for(int j=1;j<=m;j++){t[1][j]='0';}for(int j=rb[ll]+1;j<lb[rr];j++){t[1][j]='1';}printf("%s\n",t[1]+1);ll++;rr--;}for(int j=1;j<=m;j++){t[1][j]='0';}for(int j=lb[ll];j<=rb[ll];j++){t[1][j]='1';}printf("+\n");printf("%s\n",t[1]+1);}else{lmt=ans>>1;for(int i=1;i<=lmt;i++){printf("+\n");for(int j=1;j<=m;j++){t[1][j]='0';}for(int j=lb[ll];j<=rb[rr];j++){t[1][j]='1';}printf("%s\n",t[1]+1);printf("-\n");for(int j=1;j<=m;j++){t[1][j]='0';}for(int j=rb[ll]+1;j<lb[rr];j++){t[1][j]='1';}printf("%s\n",t[1]+1);ll++;rr--;}} }void solvem1(){memset(vis,0,sizeof vis);memset(cnt,0,sizeof cnt);memset(lb,0x3f,sizeof lb);for(int i=1;i<=n;i++){if(s[i][1]=='1'){if(vis[i][1]){continue;}dfs21(i,1,++cnt[1]);}}for(int i=1;i<=n;i++){if(vis[i][1]){lb[vis[i][1]]=min(lb[vis[i][1]],i);rb[vis[i][1]]=max(rb[vis[i][1]],i);}}int ans=cnt[1],lmt,ll=1,rr=cnt[1];printf("%d\n",ans);if(cnt[1]&1){lmt=ans>>1;for(int i=1;i<=lmt;i++){printf("+\n");for(int j=1;j<=n;j++){t[j][1]='0';}for(int j=lb[ll];j<=rb[rr];j++){t[j][1]='1';}for(int j=1;j<=n;j++){printf("%s\n",t[j]+1);}printf("-\n");for(int j=1;j<=n;j++){t[j][1]='0';}for(int j=rb[ll]+1;j<lb[rr];j++){t[j][1]='1';}for(int j=1;j<=n;j++){printf("%s\n",t[j]+1);}ll++;rr--;}for(int j=1;j<=n;j++){t[j][1]='0';}for(int j=lb[ll];j<=rb[ll];j++){t[j][1]='1';}printf("+\n");for(int j=1;j<=n;j++){printf("%s\n",t[j]+1);}}else{lmt=ans>>1;for(int i=1;i<=lmt;i++){printf("+\n");for(int j=1;j<=n;j++){t[j][1]='0';}for(int j=lb[ll];j<=rb[rr];j++){t[j][1]='1';}for(int j=1;j<=n;j++){printf("%s\n",t[j]+1);}printf("-\n");for(int j=1;j<=n;j++){t[j][1]='0';}for(int j=rb[ll]+1;j<lb[rr];j++){t[j][1]='1';}for(int j=1;j<=n;j++){printf("%s\n",t[j]+1);}ll++;rr--;}} }void ssolve(){printf("3\n");for(int i=1;i<=m;i++){t[1][i]='1';t[n][i]='0';r[1][i]='0';r[n][i]='1';for(int j=2;j<n;j++){t[j][i]=s[j][i];r[j][i]=s[j][i];}if(i&1){for(int j=1;j<n;j++){t[j][i]='1';}}else{for(int j=2;j<=n;j++){r[j][i]='1';}}}for(int i=1;i<=m;i++){q[1][i]=(s[1][i]!='1'?'1':'0');q[n][i]=(s[n][i]!='1'?'1':'0');for(int j=2;j<n;j++){q[j][i]='1';}}printf("+\n");for(int i=1;i<=n;i++){printf("%s\n",t[i]+1);}printf("+\n");for(int i=1;i<=n;i++){printf("%s\n",r[i]+1);}printf("-\n");for(int i=1;i<=n;i++){printf("%s\n",q[i]+1);} }void solve(){printf("3\n");for(int i=1;i<=n;i++){t[i][1]='1';t[i][m]='0';r[i][1]='0';r[i][m]='1';for(int j=2;j<m;j++){t[i][j]=s[i][j];r[i][j]=s[i][j];}if(i&1){for(int j=1;j<m;j++){t[i][j]='1';}}else{for(int j=2;j<=m;j++){r[i][j]='1';}}}for(int i=1;i<=n;i++){q[i][1]=(s[i][1]!='1'?'1':'0');q[i][m]=(s[i][m]!='1'?'1':'0');for(int j=2;j<m;j++){q[i][j]='1';}}printf("+\n");for(int i=1;i<=n;i++){printf("%s\n",t[i]+1);}printf("+\n");for(int i=1;i<=n;i++){printf("%s\n",r[i]+1);}printf("-\n");for(int i=1;i<=n;i++){printf("%s\n",q[i]+1);} }int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s[i]+1);}if(check0()){solve0();return 0;}if(check1()){solve1();return 0;}if(check2()){solve2();return 0;}if(n==1){solven1();return 0;}if(m==1){solvem1();return 0;}if(m==2){ssolve();}else{solve();}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/--BLUESKY007/p/11135879.html

總結(jié)

以上是生活随笔為你收集整理的noi.ac NA529 【神树的矩阵】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。