题目概述

给出 $n\times m$ 的 $01$ 棋盘，有 $q$ 个询问，每个询问 $k$ 表示能够修改最多 $k$ 个格子的颜色，问能选出的边长最长的 $01$ 相间且是正方形的子网格。

解题报告

刚开始想DP，然后发现其实很斯波…… $k$ 太大没什么用，最多只需要改 $nm$ 次，所以只需要枚举左上角和边长 $a$ ，求出这一块中需要改多少格子使得满足条件，假设需要 $tot$ 次，那么修改 $tot$ 次就可以造出边长为 $a$ 的正方形，刷一趟前缀 $max$ ，每次就可以直接 $O(1)$ 回答。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=200;

int n,m,te,MIN[maxn+5][maxn+5][maxn+5][2];char pic[maxn+5][maxn+5];
int ans[maxn+5][maxn+5][maxn+5][2],MAX[maxn*maxn+5];

inline void Make(){
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            int lst='0',now=pic[i][j]!=lst;MIN[i][j][j][0]=now;
            for (int k=j+1;k<=m;k++) lst^=1,now+=pic[i][k]!=lst,MIN[i][j][k][0]=now;
            lst='1';now=pic[i][j]!=lst;MIN[i][j][j][1]=now;
            for (int k=j+1;k<=m;k++) lst^=1,now+=pic[i][k]!=lst,MIN[i][j][k][1]=now;
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            for (int k=1,D=i,R=j;D<=n&&R<=m;k++,R++,D++){
                int lst=0,now=0;for (int t=i;t<=D;t++) now+=MIN[t][j][R][lst],lst^=1;MAX[now]=max(MAX[now],k);
                lst=1;now=0;for (int t=i;t<=D;t++) now+=MIN[t][j][R][lst],lst^=1;MAX[now]=max(MAX[now],k);
            }
    for (int i=1;i<=n*m;i++) MAX[i]=max(MAX[i],MAX[i-1]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%s",pic[i]+1);
    for (Make(),scanf("%d",&te);te;te--){
        int x;scanf("%d",&x);if (x>n*m) x=n*m;
        printf("%d\n",MAX[x]);
    }return 0;
}