Codeforces679C. Bear and Square Grid

n<=500,n*n的01矩阵，可以选择一个k*k的矩阵全变1，求最大1联通区域。

敢敢n^3。。模拟k*k的矩阵的位置，从左到右扫的时候，每变一个位置只会引起边界的信息变化，就记含边界的k*k矩形内的各联通块的大小以及不含边界的k*k的矩形内的0的个数，然后边移动边开个桶更新。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<stdlib.h>

 #include<math.h>

 //#include<vector>

 //#include<iostream>

 using namespace std;

 int n,K;

 #define maxn 511

 char mp[maxn][maxn];

 int id[maxn][maxn];

 int ufs[maxn*maxn],size[maxn*maxn];

 int find(int x) {return x==ufs[x]?x:(ufs[x]=find(ufs[x]));}

 void Union(int x,int y) {x=find(x),y=find(y); if (x==y) return; size[y]+=size[x]; ufs[x]=y;}

 int bud[maxn*maxn]; bool vis[maxn][maxn];

 int quex[maxn*maxn],quey[maxn*maxn],head,tail;

 const int dx[]={,-,,},dy[]={,,,-};

 void bfs(int x,int y)

 {

     vis[x][y]=; int ff=id[x][y];

     head=; tail=; quex[]=x; quey[]=y;

     while (head!=tail)

     {

         const int xx=quex[head],yy=quey[head]; head++;

         for (int i=;i<;i++)

         {

             int nx=xx+dx[i],ny=yy+dy[i];

             if (nx< || nx>n || ny< || ny>n || vis[nx][ny] || mp[nx][ny]!='.') continue;

             vis[nx][ny]=; quex[tail]=nx; quey[tail]=ny; tail++;

             int idid=id[nx][ny]; Union(idid,ff);

         }

     }

 }

 void insert(int x,int y,int &tot)

 {

     int now=id[x][y],ff=find(now);

     if (!bud[ff]) tot+=size[ff]; bud[ff]++;

 }

 void Delete(int x,int y,int &tot)

 {

     int now=id[x][y],ff=find(now);

     bud[ff]--; if (!bud[ff]) tot-=size[ff];

 }

 int main()

 {

     scanf("%d%d",&n,&K);

     for (int i=;i<=n;i++) scanf("%s",mp[i]+);

     for (int i=,tot=;i<=n;i++)

         for (int j=;j<=n;j++)

             id[i][j]=++tot;

     for (int i=;i<=n*n;i++) ufs[i]=i,size[i]=;

     for (int i=;i<=n;i++)

         for (int j=;j<=n;j++)

             if (mp[i][j]=='.' && !vis[i][j]) bfs(i,j);

     int ans=;

     for (int i=K;i<=n;i++)

     {

         memset(bud,,sizeof(bud));

         int tot=,xx=;

         for (int j=i-K+;j<=i;j++)

             for (int k=;k<=K;k++) if (mp[j][k]=='.') insert(j,k,tot);

             else xx++;

         if (K<n) for (int j=i-K+;j<=i;j++) if (mp[j][K+]=='.') insert(j,K+,tot);

         if (i>K) for (int k=;k<=K;k++) if (mp[i-K][k]=='.') insert(i-K,k,tot);

         if (i<n) for (int k=;k<=K;k++) if (mp[i+][k]=='.') insert(i+,k,tot);

         ans=max(ans,tot+xx);

         for (int k=K+;k<=n;k++)

         {

             for (int j=i-K+;j<=i;j++) xx-=(mp[j][k-K]=='X');

             for (int j=i-K+;j<=i;j++) xx+=(mp[j][k]=='X');

             if (k>K+) for (int j=i-K+;j<=i;j++) if (mp[j][k-K-]=='.') Delete(j,k-K-,tot);

             if (k<n) for (int j=i-K+;j<=i;j++) if (mp[j][k+]=='.') insert(j,k+,tot);

             if (i>K)

             {

                 if (mp[i-K][k]=='.') insert(i-K,k,tot);

                 if (mp[i-K][k-K]=='.') Delete(i-K,k-K,tot);

             }

             if (i<n)

             {

                 if (mp[i+][k]=='.') insert(i+,k,tot);

                 if (mp[i+][k-K]=='.') Delete(i+,k-K,tot);

             }

             ans=max(ans,tot+xx);

 //            cout<<i<<' '<<k<<' '<<tot<<' '<<xx<<endl;

         }

     }

     printf("%d\n",ans);

     return ;

 }