《P10719 [GESP202406 五级] 黑白格》

题目背景对应的选择、判断题试题 - GESP 202406 C 五级 - 洛谷有题题目描述小杨有一个 n 行 m 列的网格图其中每个格子要么是白色要么是黑色。小杨想知道至少包含 k 个黑色格子的最小子矩形包含了多少个格子。输入格式第一行包含三个正整数 n,m,k含义如题面所示。之后 n 行每行⼀个长度为 m 的 01 串代表网格图第 i 行格子的颜色如果为 0则对应格子为白色否则为黑色。输出格式输出一个整数代表至少包含 k 个黑色格子的最小子矩形包含格子的数量如果不存在则输出 0。输入输出样例输入 #1复制4 5 5 00000 01111 00011 00011输出 #1复制6说明/提示样例解释对于样例 1假设 (i,j) 代表第 i 行第 j 列至少包含 5 个黑色格子的最小子矩形的四个顶点为 (2,4)(2,5)(4,4)(4,5)共包含 6 个格子。数据范围对于全部数据保证有 1≤n,m≤1001≤k≤n×m。子任务编号得分n,m120≤10240n11≤m≤100340≤100Update on 2024/7/9添加了若干组 hack 数据感谢 cff_0102 的贡献。代码实现#include iostream #include string #include climits using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin n m k; int pre[105][105] {0}; for (int i 1; i n; i) { string s; cin s; for (int j 1; j m; j) { pre[i][j] pre[i - 1][j] pre[i][j - 1] - pre[i - 1][j - 1] (s[j - 1] 1); } } int ans INT_MAX; for (int x1 1; x1 n; x1) { for (int x2 x1; x2 n; x2) { for (int y1 1; y1 m; y1) { for (int y2 y1; y2 m; y2) { int sum pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] pre[x1 - 1][y1 - 1]; if (sum k) { int area (x2 - x1 1) * (y2 - y1 1); if (area ans) ans area; } } } } } if (ans INT_MAX) cout 0 \n; else cout ans \n; return 0; }