分析
由于没有修改操作,所以可以求出二维前缀和,从而达到 判断。二分边长,对每个节点单独考虑就好了,总的时间复杂度为 。
代码
#include<bits/stdc++.h> using namespace std; const int N = 5e2+100; int n,m,K; int t[N][N][26],sum[N][N][26]; bool check(int x,int y,int D){ for(int i = 0;i < 26;i++) { if(sum[x+D][y+D][i]-sum[x+D][y-1][i]-sum[x-1][y+D][i]+sum[x-1][y-1][i] > K) return false; } return true; } int main() { cin >> n >> m >> K; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { char ch;cin >> ch; t[i][j][ch-'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-1][j][k] + sum[i][j-1][k] - sum[i-1][j-1][k] + t[i][j][k]; } } } for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { int l = 1,ans = 0,r = min(m-j+1,n-i+1); while(l <= r) { int mid = l + r >> 1; if(check(i,j,mid-1)) { ans = max(ans,mid);l = mid + 1; } else r = mid - 1; } cout << ans << " "; } cout << endl; } }