突然发现自己的做法很清奇，于是就来写一篇题解了。

觉得自己还是可以，居然没用二维的东西维护答案

题意是在一个黑白矩阵上选一个小矩形染色为白，让全白的行列最多。

Part.1

考虑一种最暴力的做法，我们枚举小矩阵的左上角，暴力染色后统计行列的数量。

这个算法的时间复杂度为\(O((n-k)^2*k)\)，可以通过\(n,k<=400\)或\(n,k\)值接近的点。

但这个算法在\(k=\frac{n}{2}\)时复杂度会被卡成\(O(n^3)\)。但如果出题人数据水可能可以比正解跑的快

Part.2

先来考虑一列的答案。

如果这一列全是白色，无论在哪里时它都有贡献，先预处理出来。

考虑我们在每次枚举到\(i,j\)，往\(i,j+1\)继续枚举时，我们只用转移一列，如图。

此时只有两边的答案更新了，我们只需要考虑如何更新这两列的答案即可。

考虑对每一列做一个前缀和统计黑点的个数，每次从答案中减去左边那列的贡献，加上右边的贡献就可以了（贡献就是如果这段的黑点个数等于这列的黑点个数，答案就加一）。

Part.3

我们再来考虑如何统计一行的贡献。

如果这一行全是白色，同理的，先预处理出来。

同样的，我们在从\(i\)往\(i+1\)枚举时，也只用更新一行的答案。

考虑如何统计一行的贡献，先只看一行，我们枚举到\(i\)时包含了\([i,i+k-1]\)这个区间。

我们考虑只有这个区间包含了所有黑点时才对答案有贡献，所以我们只用记录下最左边的黑点与最右边的黑点。

如图，只有在包含了整个区间时才有贡献，如果它的区间大小没有整个区间大，那这行就永远没有贡献。

所以拓展到\(k\)行，我们只需要计算枚举到\(i\)时每行的一个区间时对答案是否有贡献即可。

但这里是不是要用到数据结构呢，实际上不用，我们这里的问题比这个要弱的多。

显然\([i,i+k-1]\)这个区间它只有它的左端点决定，我们可以只统计这个区间的左端点在哪个区间合法。

设左黑点的位置是\(L\)，右黑点的位置是\(R\)，那么整个区间能被全覆盖的充要条件是\(R-k+1\leq i\leq L\)，那么我们只需要对\([R-k+1,L]\)区间打标记即可。

这里这个步骤的的实现不需要用任何数据结构，考虑我们只用枚举的每一行进行一次这样的操作，需要\(n-k\)次，但是我们的查询操作需要每个位置进行一次，即\((n-k)^2\)次。所以我们可以直接用一个数组暴力打标记，这样是\(O(n)\)的，查询查一个点，是\(O(1)\)的，可以通过。

总时间复杂度除开读入外是\(O((n-k)\times n)\)的，可以通过。

\(Code\)

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=2005;

char s[maxn][maxn];
int sum[maxn][maxn];
int vis[maxn],n,k;
int L[maxn],R[maxn],hans,lans,ans,llans;

inline int max(const int &x,const int &y)
{
    return x>y?x:y;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(s[i][j]=='B') {L[i]=j;break;}
    for(int i=1;i<=n;++i)
        for(int j=n;j>0;--j)
            if(s[i][j]=='B') {R[i]=j;break;}
    for(int j=1;j<=n;++j)
    {
        for(int i=1;i<=n;++i)
        {
            sum[i][j]=sum[i-1][j];
            if(s[i][j]=='B') sum[i][j]++;
        }
        if(sum[n][j]==0) llans++;
    }
    for(int i=1;i<=n;++i)
        if(L[i]==0&&R[i]==0) hans++;
    for(int i=1;i<=k;++i)
    {
        if(R[i]-L[i]+1>k) continue;
        for(int j=max(1,R[i]-k+1);j<=L[i];++j)
            ++vis[j];
    }
    for(int i=1;i<=n-k+1;++i)
    {
        if(i!=1)
        {
            for(int j=max(1,R[i-1]-k+1);j<=L[i-1];++j) 
                --vis[j];
            for(int j=max(1,R[i+k-1]-k+1);j<=L[i+k-1];++j) 
                ++vis[j];
        }
        lans=llans;
        for(int j=1;j<=k;++j)
            if(sum[n][j]&&sum[i+k-1][j]-sum[i-1][j]==sum[n][j]) lans++;
        ans=max(ans,lans+vis[1]);
        for(int j=2;j<=n-k+1;++j)
        {
            if(sum[n][j-1]&&sum[i+k-1][j-1]-sum[i-1][j-1]==sum[n][j-1]) lans--;
            if(sum[n][j+k-1]&&sum[i+k-1][j+k-1]-sum[i-1][j+k-1]==sum[n][j+k-1]) lans++;
            ans=max(ans,lans+vis[j]);
        }
    }
    printf("%d\n",ans+hans);
    return 0;
}

图是不是有点丑