社团游戏

用二维前缀和记录字母个数，对于每个点二分正方形的边长，并对于每个字母进行判断，详细的注释下见代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
int read()
{
   int s=0,bj=0;
   char ch=getchar();
   while(ch<'0'||ch>'9')bj|=(ch=='-'),ch=getchar();
   while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
   return bj?-s:s;
}
void printnum(int x)
{
    if(x>9)printnum(x/10);
    putchar(x%10^48);
}
void print(int x,char ch)
{
    if(x<0){putchar('-');x=-x;}
    printnum(x);putchar(ch);
}
int n,m,K;
char ch[505];
int sum[505][505][26];//二维前缀和，sum[i][j][k]表示以（i，j）为左下角的矩形中k的个数 
int Ask(int X1,int Y1,int X2,int Y2,int num)
{
    return sum[X2][Y2][num]-sum[X1-1][Y2][num]-sum[X2][Y1-1][num]+sum[X1-1][Y1-1][num];
}
int main()
{
    n=read();m=read();K=read();
    for(int i=1;i<=n;++i)
    {
        scanf("%s",ch+1);
        for(int j=1;j<=m;++j)++sum[i][j][ch[j]-'a']; 
    }
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    for(int k=0;k<26;++k)
    sum[i][j][k]=sum[i][j][k]+sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k];//计算前缀和
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)//枚举每一个点
        {
            int l=1,r=min(n-i+1,m-j+1),mid;
            while(l<=r)//二分正方形大小 
            {
                mid=(l+r)>>1;int bj=0;
                for(int k=0;k<26;++k)if(Ask(i,j,i+mid-1,j+mid-1,k)>K){bj=1;break;}
//对于每一个字母判断是否合法 
                if(!bj)l=mid+1;
                else r=mid-1;
            }
            print(l-1,' ');
        }
        puts("");
    }
    return 0;
}