给出 $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;
}