2 条题解

  • 4
    @ 2026-10-14 9:55:04

    结论1

    我们需要将一行的所有数置为 1,然后使用这一行将每一个不全为 1 的列置为 1。

    证明:

    显然,因为最后全为 1,所以一定是由一个全为 1 的行去修改。

    结论2

    只有当整个矩阵全是 0 时才会输出 -1,否则一定有解。

    证明:

    若全是 0,显然无解,否则以定能够将一行全改为 1,然后用这一行去修改列。

    ------------------ 以下结论均为有解的情况 ------------------

    结论3

    我们将全改为 1 的这一行称作第 ii 行(下同),则若第 ii 列有至少一个 1,修改的花费为第 ii 行零的个数。

    证明:

    我们可以用在第 ii 列中存在 1 的这一行去修改第 ii 行上所有 0 所在的列即可。

    那有没有可能在修改时会替换掉这个第 ii 列上的一呢?

    考虑这组数据:

    5
    00100
    00000
    11001
    00000
    00000
    

    显然,我们发现直接拿第一行去修改第三列会替换掉第一行上的 1,但我们可以先去改第四列再改第三列,因此这种情况对答案没有影响。

    结论4

    若第 ii 列没有 1,修改的花费为第 ii 行零的个数 +1。

    证明:

    首先,我们已经确保此时至少有一个 1,假设这个 1 的位置为 (j,k)(j,k),我们一定能将其转化到 (k,i)(k,i)(将第 jj 行复制到第 ii 列),然后就能按照结论 3 解决。

    那有没有可能在复制时会把 (i,i)(i,i) 上的 1 置为 0 了呢?

    没有。因为结论四的前置条件是第 ii 行没有 1,因此 (i,i)(i,i) 一定是 0。

    那有没有可能在复制时又会把 (i,i)(i,i) 上的 0 置为 1 了呢?

    没有。(i,i)(i,i) 置为 1 的前提是 (j,i)(j,i) 为 1,不符合第 ii 列没有 1 的前置条件。

    因此这个题就是将一行修改为全是 1 的最小花费再加上不是全为 1 的列的个数,于是这个题就做完了. . . . . .吗?

    有没有可能在修改行时将一个全 1 列破坏?

    没有。因为结论 3 在修改行时只会修改 0 所在的列,不会破坏全 1 列,而结论 4 在修改行时只会修改全为 0 的第 ii 列,也不会破坏全 1 列。

    有没有可能在修改行时会生成全 1 列?

    这对结论没有影响。因为修改第 ii 行时若会生成全 1 列,用来修改的行必须要全为 1,因此改第 ii 行不是最优,对答案没有影响。

    然后这个题就做完了。

    code:

    #include<bits/stdc++.h>
    using namespace std;
    const int N=1005;
    int n,b[N],x,a[N][N];
    char ch;
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			cin>>ch;
    			a[i][j]=ch-'0';
    			b[j]+=a[i][j];
    			x+=a[i][j];
    		}
    	}
    	if(x==0){
    		cout<<-1;
    		return 0;
    	}
    	int minn=0x3f3f3f3f;
    	for(int i=1;i<=n;i++){
    		int sum=0;
    		if(b[i]==0) sum++;
    		for(int j=1;j<=n;j++){
    			if(a[i][j]==0) sum++;
    		}
    		minn=min(minn,sum);
    	}
    	for(int i=1;i<=n;i++){
    		if(b[i]==n) minn--;
    	}
    	cout<<minn+n;
    	return 0;
    }
    

    AC记录

    本文同步发表至洛谷(虽然不是我搬的)

    • 1
      @ 2026-10-14 9:01:09

      SOLUTION

      题意中赋值即为把某行赋值到某列上。

      首先特判全 00 无解,全 11 无需操作。

      要使某不全为 00 的列变成全 11,一定需要一个全 11 的行。

      于是显然有枚举 i∈[1,n]i \in [1,n] 作为那个全 11 的行,若其非全 11 则设法补全。发现补全第 ii 行需要第 ii 列有 11 存在,其操作次数为 n−∑j∈[1,n]ai,jn-\sum_{j \in [1,n]} a_{i,j},说人话就是这一行 00 的个数。

      有了一个全 11 的行,把整个方阵赋值成 11 的操作次数即为不全为 11 的列的个数,显然前一步不会影响这一步。

      交上去得了 9090 pts,这是为什么?

      HACK

      发现如果第 ii 列没有 11,那就把任意一个有 11 的行赋值过来,次数加一。存在这样的数据,使得一行补全的次数很少,却不直接存在能为其赋值的列。

      CODE

      #include<bits/stdc++.h>
      using namespace std;
      #define int long long
      #define fi first
      #define se second
      int T,n,m;
      int a[1010][1010];
      int cl[1010];
      signed main(){
          ios::sync_with_stdio(0);
          cin.tie(0),cout.tie(0);
          cin>>n;
          int Fl=0;
          for(int i=1;i<=n;i++){
              for(int j=1;j<=n;j++){
                  char c;
                  cin>>c;
                  a[i][j]=c-'0';
                  Fl|=a[i][j];
              }
          }
          if(!Fl){
              cout<<"-1\n";
              return 0;
          }
          int sc=0;
          for(int j=1;j<=n;j++){
              int fl=1;
              cl[j]=0;
              for(int i=1;i<=n;i++){
                  fl&=a[i][j];
                  cl[j]|=a[i][j];
              }
              sc+=1-fl;
          }
          int ans=114514;
          for(int i=1;i<=n;i++){
              int s=0;
              for(int j=1;j<=n;j++){
                  s+=1-a[i][j];
              }
              if(s==0) ans=min(ans,sc);
              else if(cl[i]) ans=min(ans,sc+s);
              else ans=min(ans,sc+s+1);//加上本行即可 90->100
          }
          cout<<ans<<'\n';
          return 0;
      }
      
      • 1

      信息

      ID
      898
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      (无)
      递交数
      44
      已通过
      8
      上传者