携程的网站建设,ps做好的网站如何做链接,成都发布最新消息,wordpress文章加预览图题目描述
小杨有一个 n 行 m 列的网格图#xff0c;其中每个格子要么是白色#xff0c;要么是黑色。
小杨想知道至少包含 k 个黑色格子的最小子矩形包含了多少个格子。
输入格式
第一行包含三个正整数 n,m,k#xff0c;含义如题面所示。
之后 n 行#xff0c;每行⼀个…题目描述
小杨有一个 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≤100
做法一暴力
#include iostream
using namespace std;int s[110][110];
int main()
{int n,m,k;cinnmk;for(int i1;in;i)for(int j1;jm;j){char c;cinc;s[i][j]s[i][j-1]s[i-1][j]-s[i-1][j-1](c1);}int maxn2e9;for(int r11;r1n;r1)for(int r2r1;r2n;r2)for(int c11;c1m;c1)for(int c2c1;c2m;c2){int area(r2-r11)*(c2-c11);int bs[r2][c2]-s[r1-1][c2]-s[r2][c1-1]s[r1-1][c1-1];if(bkareamaxn)maxnarea;}cout(maxn2e9?maxn:0);return 0;
}
搞一个二位前缀和暴力打擂台无了但是O(n⁴)这道题数据小能过。
---------------------------------------------------------------------------------------------------------------------------------
做法二二分
#include iostream
using namespace std;int n,m,k,r1,r2,s[110][110];
int f(int a,int b,int c,int d)
{return s[b][d]-s[a-1][d]-s[b][c-1]s[a-1][c-1];
}
bool check(int mid)
{for(int l1;lmid-1m;l){int rlmid-1;int bf(r1,r2,l,r);if(bk)return true;}return false;
}
int bs()
{int l1,rm;while(lr){int mid(lr)/2;if(check(mid))rmid;elselmid1;}return l;
}
int main()
{cinnmk;for(int i1;in;i)for(int j1;jm;j){char c;cinc;s[i][j]s[i][j-1]s[i-1][j]-s[i-1][j-1](c1);}int minx2e9;for(r11;r1n;r1)for(r2r1;r2n;r2){if(f(r1,r2,1,m)k)continue;int wbs();int area(r2-r11)*w;if(areaminx)minxarea;}cout(minx2e9?0:minx);return 0;
}
做法 1.二层循环固定r1和r2。 2.二分查找找宽度即c1和c2差。 3.check里枚举所有可能有一个满足就return true。 4.二层循环*二分*check复杂度O(n³logn)。
细节 1.写一个f函数算二维区间和简洁还能偷懒o(*▽*)ブ 2.由于是二分必须保证两头至少一个是true不然会出错所以要提前判断这个r1和r2的最大区间够不够k个不够continue。
