loj#6030. 「雅礼集训 2017 Day1」矩阵(贪心 构造)
程序员文章站
2022-04-28 14:00:27
题意 "链接" Sol ~~自己都不知道自己怎么做出来的系列~~ 不难观察出几个性质: 1. 最优策略一定是先把某一行弄黑,然后再用这一行去覆盖不是全黑的列 2. 无解当且仅当无黑色。否则第一个黑色所在的行$i$可以先把第$i$列弄出一个黑色,接下来第$i$列的黑色可以把第$i$行全部弄成黑色。 然 ......
题意
sol
自己都不知道自己怎么做出来的系列
不难观察出几个性质:
- 最优策略一定是先把某一行弄黑,然后再用这一行去覆盖不是全黑的列
- 无解当且仅当无黑色。否则第一个黑色所在的行\(i\)可以先把第\(i\)列弄出一个黑色,接下来第\(i\)列的黑色可以把第\(i\)行全部弄成黑色。
然后直接算出把每一行弄黑的步数取个min就行了。
代码里面有注释。
#include<bits/stdc++.h> #define pair pair<int, int> #define mp(x, y) make_pair(x, y) #define fi first #define se second #define ll long long #define ull unsigned long long #define fin(x) {freopen(#x".in","r",stdin);} #define fout(x) {freopen(#x".out","w",stdout);} using namespace std; const int maxn = 1001, inf = 1e9 + 1, mod = 1e9 + 7; const double eps = 1e-9, pi = acos(-1); template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;} template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;} template <typename a, typename b> inline ll add(a x, b y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;} template <typename a, typename b> inline void add2(a &x, b y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);} template <typename a, typename b> inline ll mul(a x, b y) {return 1ll * x * y % mod;} template <typename a, typename b> inline void mul2(a &x, b y) {x = (1ll * x * y % mod + mod) % mod;} inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n; char s[maxn][maxn]; int fullrow[maxn], haverow[maxn], fullcol[maxn], havecol[maxn];//full:每行每列是否全为1 / have:是否至少有一个1 signed main() { n = read(); for(int i = 1; i <= n; i++) scanf("%s", s[i] + 1); bool flag = 0; fill(fullrow + 1, fullrow + n + 1, 1); fill(fullcol + 1, fullcol + n + 1, 1); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(s[i][j] == '#') flag = 1, haverow[i] = 1, havecol[j] = 1; else fullrow[i] = 0, fullcol[j] = 0; if(!flag) return puts("-1"), 0; int ans = inf; for(int i = 1; i <= n; i++) { int now = 0; if(fullrow[i]) { for(int j = 1; j <= n; j++) now += (!fullcol[j]);//如果第i行全为黑,答案就加上不为黑的列数 chmin(ans, now); continue; } if(!havecol[i]) { if(!haverow[i]) continue; else now++;//用该行的一个黑去染黑对应的列 } for(int j = 1; j <= n; j++) { if(fullcol[j]) continue; if(s[i][j] == '.') now += 2; else now++; } chmin(ans, now); } cout << ans; return 0; }
下一篇: python的基本数据类型(一)
推荐阅读
-
loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)
-
loj#6029. 「雅礼集训 2017 Day1」市场(线段树)
-
loj#6030. 「雅礼集训 2017 Day1」矩阵(贪心 构造)
-
loj#6032. 「雅礼集训 2017 Day2」水箱(并查集 贪心 扫描线)
-
loj#6029. 「雅礼集训 2017 Day1」市场(线段树)
-
loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)
-
loj#6030. 「雅礼集训 2017 Day1」矩阵(贪心 构造)
-
loj#6032. 「雅礼集训 2017 Day2」水箱(并查集 贪心 扫描线)
-
ZCMU-2035 #6035. 「雅礼集训 2017 Day4」洗衣服 贪心+思路