2 条题解
-
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; }
信息
- ID
- 898
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 44
- 已通过
- 8
- 上传者