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/)。特判即可。

完整代码

#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;
}

希望能帮助到大家！

首发：2022-08-19 14:11:03