题意：
现在有一个n*m的矩阵A，在A中找一个H*H的正方形，使得其面积最大且该正方形元素的和不大于 limit。
思路：水题
预处理矩形元素和，然后二分枚举最大边长，然后把这边长在整个矩形中试一遍（O(n*m)）看是否符合。总时间复杂度O(n*m*log(min(n,m))) 可暴
code：
#include<cstdio>#include<iostream>#include<sstream>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<queue>#include<map>#include<set>#include<cmath>#include<cctype>#include<cstdlib>using namespace std;#define INF 0x3f3f3f3f#define PI acos(-1.0)#define mem(a, b) memset(a, b, sizeof(a))#define mod 1000000007typedef pair<int,int> pii;typedef long long LL;//——————————const int maxn = 1005;int n,m,limit;int pre[maxn][maxn];int maze[maxn][maxn];void deal(){memset(pre, 0, sizeof(pre));for(int i = 1; i <= m; i++){pre[1][i] = pre[1][i-1] + maze[1][i];}for(int i = 2; i <= n; i++){int tmp = 0;for(int j = 1; j <= m; j++){tmp += maze[i][j];pre[i][j] = pre[i-1][j] + tmp;}}}void init(){scanf("%d%d%d",&n,&m,&limit);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){scanf("%d",&maze[i][j]);}}deal();}bool ok(int x){for(int i = 1; i <= n-x+1; i++){for(int j = 1; j <= m-x+1; j++){if(pre[i+x-1][j+x-1] – pre[i-1][j+x-1] – pre[i+x-1][j-1] + pre[i-1][j-1] <= limit)return true;}}return false;}void solve(){int lb = 0, ub = min(n,m);while(lb <= ub){int mid = (lb+ub) / 2;if(ok(mid)) lb = mid+1;else ub = mid-1;}printf("%d\n",ub * ub);}int main(){int t;scanf("%d",&t);while(t–){init();solve();}return 0;}
我的二分出了点小问题，，真实比了狗了…T_T
会让你的心态更平和更坦然，
