题目描述
在民风淳朴的雏见泽，号称能“完美犯罪”的天才牛牛，又开始和社团的萌妹子牛妹玩起了游戏。
在今天的游戏中，牛牛将会得到一个n×mn\times mn×m且全为小写字母的矩阵，他可以从矩阵中任选一块正方形，但必须保证该正方形中任意一类小写字母个数之和不能超过kkk，换而言之，在该正方形中，‘a’字符个数不能超过kkk，‘b’字符个数不能超过kkk，…，‘z’字符个数不能超过kkk。
现在牛牛想知道，以(i,j)(i,j)(i,j)为左上角且符合以上要求的正方形中，边长最大的是多少？
输入描述:
第一行三个正整数nnn,mmm,kkk，其中：n≤500n\leq500n≤500，m≤500m\leq500m≤500，k≤109k\leq10^{9}k≤109。
接下来nnn行，每行mmm个小写字母。
输出描述:
输出nnn行，每行mmm个数字。其中第iii行第jjj个数字表示，以(i,j)(i,j)(i,j)为左上角且符合题目要求的正方形的最大边长。
示例1 输入 复制
3 3 2 aaa bcd efg
输出 复制
2 2 1 2 2 1 1 1 1
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int maxn = 1e3 + 10; int dp[30][maxn][maxn]; char a[maxn][maxn]; int ans[maxn][maxn]; int n, m, k; void init() { for(int k = 0; k < 26; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) dp[k][i][j] = dp[k][i - 1][j] + dp[k][i][j - 1] - dp[k][i - 1][j - 1] + (a[i][j] == k + 'a'); } } } bool judge(int x1, int y1, int x2, int y2) { for(int i = 0; i < 26; i++) { if(dp[i][x2][y2] - dp[i][x1 - 1][y2] - dp[i][x2][y1 - 1] + dp[i][x1 - 1][y1- 1] > k) return false; } return true; } void solve() { 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), ans = 1; while(l <= r) { int mid = l + r >> 1; if(judge(i, j, i + mid - 1, j + mid - 1)) l = mid + 1, ans = mid; else r = mid - 1; } cout << ans << " "; } cout << endl; } } int main() { cin >> n >> m >> k; for(int i = 1; i <= n; i++) cin >> a[i] + 1; init(); solve(); return 0; }