题目链接
万恶的多校，今天又自闭了，一个题交了18发wa，心态炸裂
到现在回头补，才写出来。
题目意思：一个nn的大矩阵，这个大矩阵，只包含 ‘W’ 和 ‘B’ 两种字母， 现在，你只能选择一个 kk 的小矩阵，将这个小矩阵中的字母全部变成 ‘W’ 之后，这个大矩阵的整行，整列全部是 ‘W’ 的个数最多， 求这个数。
做法：以样例一来说事
4 2
BWWW
WBBW
WBBW
WWWB
首先，我们先只考虑一个方向的一行
如图，对于第二行只有满足这个的一个条件 sum(1,i-k) + sum(i+1,n) + k == n， 取矩形时包含这行(或列)才会对答案有贡献
同样， 对于一列也差不多是这样
再来，对于整个大矩阵
我们不是要找个 k*k 的矩阵吗， 我们看向上图中矩阵的右下角
单单只看这个点**(i, j)**
对于 x 方向 sum(1, j-k) + sum(j+1,n) + k == n 第一个答案
对于 y 方向 sum(1, i-k) + sum(i+1,n) + k == n 第二个答案
再来看右下角的上一个点 (i-1,j)
对于 x 方向 满足条件 第三个答案
对于 y 方向 如果把这个考虑进去，不会重复吗
再来看右下角的左边一个点 (i,j-1)
同样 对于 x 方向 我们不能考虑进去
对于 y 方向 满足条件 第四个答案
对于这个2*2的矩阵的最后一个点 (i-1,j-1)
我们要考虑吗？？？
这样的一顿思考后，我们就找到了一种做法，枚举每个矩阵，我们只要考虑这个矩阵的右下角的 x,y 方向， 右下角的正上方的那些点的 x 方向， 右下角的正左方的 y 方向
但是，按这样的想法去写的话，样例2是过不了的 放心不是我的想法错误
会发现，有些行或者列, 即使我们不去改，它们也早就都是 ‘W’ 了，所以我们要统计一下
完
以上这些想法怎么实现呢，前缀和， 全部都是前缀和
代码：
#include <bits/stdc++.h>
const int maxn = 2005;
using namespace std;
typedef long long ll;
int n, k;
char str[maxn][maxn];
int yuanx[maxn][maxn], yuany[maxn][maxn]; //统计x y 方向的前缀和
int ansx[maxn][maxn], ansy[maxn][maxn];
//统计每个点 x 方向的前缀和， 但是这个前缀和要延 y 方向求前缀和
//统计每个点 y 方向的前缀和， 但是这个前缀和要延 x 方向求前缀和
int yix[maxn], yiy[maxn];
//最没改变时， x方向 就都是 'W'
//最没改变时， y方向 就都是 'W'
int main()
{
scanf("%d%d", &n, &k);
for(int i=1; i<=n; i++){
scanf("%s", str[i]+1);
for(int j=1; j<=n; j++){
yuanx[i][j] = yuanx[i][j-1];
yuany[i][j] = yuany[i-1][j];
if(str[i][j] == 'W')
yuanx[i][j]++, yuany[i][j]++; //统计前缀和
}
}
for(int i=1; i<=n; i++){
yix[i] = yix[i-1], yiy[i] = yiy[i-1];
if(yuanx[i][n] == n) //不改变，i行就已经都是白色的
yix[i]++;
if(yuany[n][i] == n) //不改变，i列就已经都是白色的
yiy[i]++;
}
int res = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
ansx[i][j] = ansx[i-1][j]; //x 向的答案向y方向延续
ansy[i][j] = ansy[i][j-1];
if(j >= k && yuanx[i][j-k] + (yuanx[i][n]-yuanx[i][j]) + k == n)
ansx[i][j]++;
if(i >= k && yuany[i-k][j] + (yuany[n][j]-yuany[i][j]) + k == n)
ansy[i][j]++;
if(i >= k && j >= k){
int t = ansx[i][j]- ansx[i-k][j] + ansy[i][j] - ansy[i][j-k]; //与改变才产生的答案
t = t + yix[n] - (yix[i] - yix[i-k]) + yiy[n] - (yiy[j] - yiy[j-k]); //这个矩阵，之外，不改变也会增加答案
res = max(res, t);
}
}
}
printf("%d
", res);
return 0;
}