NC209824. 社团游戏
描述
在民风淳朴的雏见泽，号称能“完美犯罪”的天才牛牛，又开始和社团的萌妹子牛妹玩起了游戏。
在今天的游戏中，牛牛将会得到一个且全为小写字母的矩阵，他可以从矩阵中任选一块正方形，但必须保证该正方形中任意一类小写字母个数之和不能超过
，换而言之，在该正方形中，‘a’字符个数不能超过
，‘b’字符个数不能超过
，…，‘z’字符个数不能超过
。
现在牛牛想知道，以为左上角且符合以上要求的正方形中，边长最大的是多少？
输入描述
第一行三个正整数
,
,
，其中：
，
，
。
接下来
输出描述
输出
行第
个数字表示，以
为左上角且符合题目要求的正方形的最大边长。
示例1
输入:
3 3 2 aaa bcd efg
输出:
2 2 1 2 2 1 1 1 1
C++(clang++11) 解法, 执行用时: 230ms, 内存消耗: 27552K, 提交时间: 2021-03-04 20:45:10
#include<bits/stdc++.h>
using namespace std;
char mp[505][505];
int s[26][505][505],n,m,k;
inline bool ck(int x,int y,int l){
for(int i=0;i<26;++i)
if(s[i][x][y]-s[i][x-l][y]-s[i][x][y-l]+s[i][x-l][y-l]>k)return 0;
return 1;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;++i)
cin>>mp[i]+1;
for(int l=0;l<26;++l)
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
s[l][i][j]=s[l][i-1][j]+s[l][i][j-1]-s[l][i-1][j-1]+(mp[i][j]==l+'a'?1:0);
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)+1,mid;
while(l+1<r){
mid=l+r>>1;
if(ck(i+mid-1,j+mid-1,mid))l=mid;
else r=mid;
}cout<<l<<' ';
}
cout<<'\n';
}
}