CF1720C 题解

## 前言 [题目传送门！](https://www.luogu.com.cn/problem/CF1720C) [更好的阅读体验？](https://liangbowen.blog.luogu.org/solution-cf1720c) 赛时锁题后看别人代码，怎么都和我想法不一样？幸好没有被 hack。 ## 思路 以下把 L 字形的覆盖网格，直接称为 L。 贪心思考，我们想让每次 L 覆盖的 $1$ 的数量少一些。 手玩一遍样例，我们发现：第一次 L 可能会覆盖多几个 $1$，**之后每次必定可以只覆盖一个** $1$。 为什么呢？看这张图。  也就是说，假设第一次覆盖了 $k$ 个 $1$，整张地图共有 $x$ 个 $1$，那么总使用次数就是 $(x - k) + 1$。 上面这个可以理解为：第一次用 $1$ 个 L，之后每次消耗 $(x - k)$ 个 $1$，即 $(x - k)$ 个 L。共 $(x - k + 1)$ 个 L。 所以，我们应该使得 $k$ 最小。 只需对第一次 L 分情况考虑即可。枚举每一个 $2 \times 2$ 的矩阵：  然后模拟就搞定了。 需要注意，如果整张地图全是 $0$，答案应该为 $0$。特判即可。 ## 完整代码 ```cpp #include <iostream> #include <cstdio> #define endl putchar('\n') using namespace std; void fastio() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); } const int N = 505; int a[N][N]; void solve() { int n, m, sum = 0, minn = 114514; cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { char x; cin >> x; a[i][j] = (x == '1'), sum += a[i][j]; //sum 统计 1 的个数 } for (int i = 2; i <= n; i++) for (int j = 2; j <= m; j++) { //cnt 表示 2*2 方格内有多少个 1 int cnt = a[i-1][j-1] + a[i-1][j] + a[i][j-1] + a[i][j]; if (cnt == 0) continue; //没有 1 说明无法构成 L 型 if (cnt == 1) minn = min(minn, 1); //一个 1 最少也要包含这个 1 否则不合法 if (cnt == 2) minn = min(minn, 1); //两个 1 仍然可以使 L 只覆盖一个 1 if (cnt == 3) minn = min(minn, 2); //三个 1 显然必须覆盖两个 if (cnt == 4) minn = min(minn, 3); //四个 1 明显覆盖 3 个 } if (minn == 114514) {cout << 0 << '\n'; return;} //如果一个 L 都没法覆盖，就是 0 cout << sum - minn + 1 << '\n'; //否则，第一次用 1 个 L，之后每次消耗 (sum - minn) 个 1，共 (sum - minn + 1) 个 L } int main() { fastio(); int T; cin >> T; while (T--) solve(); return 0; } ``` 希望能帮助到大家！