题解 P1387 【最大正方形】
update: 前缀和加二分的解释及程序
水题水题水题
暴力出奇迹
Ps: 有评论区问能不能用二分做 答案是 可以 的 代码解释请看下
本篇题解介绍纯暴力方法。不会炸，还挺快(不会DP 直说嘛)
【题外话】
考场上不要盲目地追求正解！先全部写完暴力(可以和正解对拍)，再慢慢研究正解。不能在一题上耗费过多时间，其实有时候你辛辛苦苦写了个正解，某个地方写挂了，那还不如人家乱打的暴力.
【思路】
枚举每一个点作为所选正方形的左上角的点，然后枚举正方形边长，逐一判断。
【优化】
-
边长倒着枚举，
min(n,m) 作为上界(因为正方形边长最大就是min(n,m) )，枚举到当前的最大边长(不是最优解即使符合条件也是无济于事)。 -
逐一进行判断，一旦找到
0 立刻将双重循环break 。 -
假如可行(即这个边长的正方形符合条件)则：
1. 直接将最优解替换(由于下界为当前最大边长)。2. 将枚举长度的那一段break (由于是倒着枚举)。
Code：
#include <bits/stdc++.h>
#define re register int
using namespace std;
bool f[202][202]={0},p;
int n,m,i,j,k,x,y,ans=0;
int main()
{
scanf("%d%d",&n,&m);
for (re i=0; i<n; i++)
for (re j=0; j<m; j++)
scanf("%d",&f[i][j]); //读入不解释
for (re i=0; i<n; i++)
for (re j=0; j<m; j++)
for (re k=min(n,m); k>ans; k--)//优化1
{
p=1;
for (re x=i; x<i+k; x++) //逐个判断
{
for (re y=j; y<j+k; y++)
if (!f[x][y]) //不是1的话
{
p=0; break; //标记，跳出循环，优化2
}
if (!p) break; //不符合没必要接着做，优化2
}
if (p) //符合条件的话
{
ans=k; break; //优化3
}
}
printf("%d",ans); //输出
return 0;
}【一些思考】
假如n再大些，我们可以用前缀和，分为以下两种：
-
O(n^4) 的，设f[i][j] = 输入数据中第i行的前j个的和。那么枚举的时候只需枚举行，要是f[x][j+k] - f[x][j] (即这一行1 的个数)< K 那么就不符合条件。 -
O(n^3) 的，设f[i][j] = 输入数据中从(1,1) 到(i,j) 的总和。求前缀和的时候可以
f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a[i][j] (
a[i][j] 当前值)，如下图：黄色是重叠部分，紫色是当前值，两个加上后减去重叠再加上当前值即为我们要求的。
判断时只需要判断 (
i,j 表示正方形左上角的坐标;k 为正方形边长)
是否
由于重复所以要加上去，稍微想一下就出来了。
【二分优化】
- 有同学提到可以二分优化，我认为这是一个非常棒的想法
(毕竟我没想到) - 为什么可以二分?
因为不同边长是否符合条件具有单调性
意思就是，设答案为
-
大于
ans 的肯定不符合条件(即有0),不然那个大于ans 又符合条件的才是真正的答案(这是个假的ans ), -
小于
ans 的肯定都符合条件,因为边长为ans 的正方形包含了边长<=ans 的正方形，所以边长<ans 的正方形符合条件(即全是1)是边长为ans 的正方形符合条件的必要不充分条件。即
<x 的不符合,x 必然不符合,<x 符合，x 也有可能不符合(x= 边长)综上,得到小于
ans 的都符合。
有了单调性后就可以二分优化啦！
二分边长
这里给出上面
#include <bits/stdc++.h>
using namespace std;
int n, m, ans = 0, x, f[205][205];
int main() {
scanf("%d%d", &n, &m);
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) {
scanf("%d", &x);
f[i][j]= f[i-1][j]+f[i][j-1]-f[i-1][j-1]+x;
}
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j) {
int l = 0, r = min(n,m);
while (l<=r) {
int mid = (l+r)>>1;
if (i+mid>n || j+mid>m || f[i+mid][j+mid]-f[i+mid][j]-f[i][j+mid]+f[i][j] < mid*mid) r = mid-1;
else l = mid+1;
}
if (f[i+r][j+r]-f[i+r][j]-f[i][j+r]+f[i][j] == r*r) ans = max(ans, r);
}
cout << ans;
return 0;
}实测已AC,要注意的是二分后还要再判断一下,不然就只有40分
O(n^2) 的话就去看楼下的dp吧。
我的虽然不是最优的，却是最好理解的！
如果您满意的话右上角的赞
加了
修了