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; }本文同步发表至洛谷(虽然不是我搬的)
-
1
SOLUTION
题意中赋值即为把某行赋值到某列上。
首先特判全 无解,全 无需操作。
要使某不全为 的列变成全 ,一定需要一个全 的行。
于是显然有枚举 作为那个全 的行,若其非全 则设法补全。发现补全第 行需要第 列有 存在,其操作次数为 ,说人话就是这一行 的个数。
有了一个全 的行,把整个方阵赋值成 的操作次数即为不全为 的列的个数,显然前一步不会影响这一步。
交上去得了 pts,这是为什么?
HACK
发现如果第 列没有 ,那就把任意一个有 的行赋值过来,次数加一。存在这样的数据,使得一行补全的次数很少,却不直接存在能为其赋值的列。
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
- 上传者