社团游戏-题解

题目描述
在民风淳朴的雏见泽，号称能“完美犯罪”的天才牛牛，又开始和社团的萌妹子牛妹玩起了游戏。

在今天的游戏中，牛牛将会得到一个n\times mn×m且全为小写字母的矩阵，他可以从矩阵中任选一块正方形，但必须保证该正方形中任意一类小写字母个数之和不能超过kk，换而言之，在该正方形中，‘a’字符个数不能超过kk，‘b’字符个数不能超过kk，…，‘z’字符个数不能超过kk。

现在牛牛想知道，以(i,j)(i,j)为左上角且符合以上要求的正方形中，边长最大的是多少？
思路：枚举横的，枚举竖的，暴力就行。
代码：

//社团游戏
#include <bits/stdc++.h>
using namespace std;
int sum[27][505][505];
char s[505][505];
int n,m,k;
int ans[505][505];
bool jud(int x,int y,int p,int q){
    for(int l=0;l<26;++l){
        if(sum[l][p][q]-sum[l][p][y-1]-sum[l][x-1][q]+sum[l][x-1][y-1]>k) return false;
    }
    return true;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
    for(int l=0;l<26;++l){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                sum[l][i][j]=-sum[l][i-1][j-1]+sum[l][i][j-1]+sum[l][i-1][j]+(s[i][j]-'a'==l);
            }
        }
    }
    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);
            while(l<=r){
                int mid=(l+r)>>1;
                if(jud(i,j,i+mid-1,j+mid-1)){
                    l=mid+1;
                } else{
                    r=mid-1;
                }
            }
            ans[i][j]=r;
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
             printf("%d ",ans[i][j]);   
        }
        printf("\n");
    }


}