2 条题解
-
4
结论1
我们需要将一行的所有数置为 1,然后使用这一行将每一个不全为 1 的列置为 1。
证明:
显然,因为最后全为 1,所以一定是由一个全为 1 的行去修改。
结论2
只有当整个矩阵全是 0 时才会输出 -1,否则一定有解。
证明:
若全是 0,显然无解,否则以定能够将一行全改为 1,然后用这一行去修改列。
------------------ 以下结论均为有解的情况 ------------------
结论3
我们将全改为 1 的这一行称作第 行(下同),则若第 列有至少一个 1,修改的花费为第 行零的个数。
证明:
我们可以用在第 列中存在 1 的这一行去修改第 行上所有 0 所在的列即可。
那有没有可能在修改时会替换掉这个第 列上的一呢?
考虑这组数据:
5 00100 00000 11001 00000 00000显然,我们发现直接拿第一行去修改第三列会替换掉第一行上的 1,但我们可以先去改第四列再改第三列,因此这种情况对答案没有影响。
结论4
若第 列没有 1,修改的花费为第 行零的个数 +1。
证明:
首先,我们已经确保此时至少有一个 1,假设这个 1 的位置为 ,我们一定能将其转化到 (将第 行复制到第 列),然后就能按照结论 3 解决。
那有没有可能在复制时会把 上的 1 置为 0 了呢?
没有。因为结论四的前置条件是第 行没有 1,因此 一定是 0。
那有没有可能在复制时又会把 上的 0 置为 1 了呢?
没有。 置为 1 的前提是 为 1,不符合第 列没有 1 的前置条件。
因此这个题就是将一行修改为全是 1 的最小花费再加上不是全为 1 的列的个数,于是这个题就做完了. . . . . .吗?
有没有可能在修改行时将一个全 1 列破坏?
没有。因为结论 3 在修改行时只会修改 0 所在的列,不会破坏全 1 列,而结论 4 在修改行时只会修改全为 0 的第 列,也不会破坏全 1 列。
有没有可能在修改行时会生成全 1 列?
这对结论没有影响。因为修改第 行时若会生成全 1 列,用来修改的行必须要全为 1,因此改第 行不是最优,对答案没有影响。
然后这个题就做完了。
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; }本文同步发表至洛谷(虽然不是我搬的)
信息
- ID
- 898
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 44
- 已通过
- 8
- 上传者