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记录

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

    信息

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