CF1720C 题解
2022/8/27 23:22:51
本文主要是介绍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
这篇关于CF1720C 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享