codeforces 680E Bear and Square Grid 巧妙暴力

这个题是个想法题

先预处理连通块，然后需要用到一种巧妙暴力，即0变1，1变0，一列列添加删除

复杂度O（n^3)

#include <cstdio>

#include <iostream>

#include <ctime>

#include <vector>

#include <cmath>

#include <map>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long LL;

const int N=5e2+;

const int INF=0x3f3f3f3f;

const int mod=1e9+;

char s[N][N];

int vis[N][N],sum[N][N],now[N*N],cnt,n,k,bcc[N*N];

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

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

void dfs(int x,int y){

  vis[x][y]=cnt,++bcc[cnt];

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

    int nx=x+dx[i],ny=y+dy[i];

    if(nx<||nx>n||ny<||ny>n||s[nx][ny]=='X'||vis[nx][ny])continue;

    dfs(nx,ny);

  }

}

int cur;

void del(int x,int y){

   if(!vis[x][y])return;

   if((--now[vis[x][y]])==)cur-=bcc[vis[x][y]];

}

void add(int x,int y){

  if(!vis[x][y])return;

  if((++now[vis[x][y]])==)cur+=bcc[vis[x][y]];

}

int cal(int x,int y){

  return sum[x][y]-sum[x-k][y]-sum[x][y-k]+sum[x-k][y-k];

}

int main()

{

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

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

    scanf("%s",s[i]+);

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

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

      sum[i][j]=sum[i-][j]+sum[i][j-]-sum[i-][j-];

      sum[i][j]+=s[i][j]=='.'?:;

    }

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

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

      if(s[i][j]=='.'&&!vis[i][j])++cnt,dfs(i,j);

   int ret=;

   for(int i=;i<=n-k+;++i){

      cur=,memset(now,,sizeof(now));

      for(int p=i-;p<=i+k;++p)

        for(int q=;q<=k+;++q)

           add(p,q);

      del(i-,k+),del(i+k,k+);

      ret=max(ret,cur+k*k-cal(i+k-,k));

      for(int p=;p<=n-k+;++p){

         for(int q=i;q<=i+k-;++q)

           del(q,p-),add(q,p+k);

         del(i-,p-);del(i+k,p-);

         add(i-,p+k-);add(i+k,p+k-);

         ret=max(ret,cur+k*k-cal(i+k-,p+k-));

      }

   }

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

   return ;

}