說是一個(gè)k的方塊，里面的都可以變成點(diǎn)，問最大的聯(lián)通塊。
2A的原因是這個(gè)有意思的刪點(diǎn)，聯(lián)通塊里的點(diǎn)不能有一個(gè)不在就直接刪除，而是要標(biāo)記一下，都出去了才能刪除。機(jī)智。
大概思路就是，預(yù)處理每個(gè)聯(lián)通快，完事把這個(gè)里面所有點(diǎn)加一遍，容斥+二維預(yù)處理前綴和求出塊內(nèi)有多少是變過來的點(diǎn)。最后直接一步步忘向右滑動(dòng)即可。磨磨唧唧寫了半個(gè)多小時(shí)。。。

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <iostream>using namespace std; char mp[510][510]; int vis[510][510]; int are_num[250050]; int sum[510][510]; int are_vis[250050]; int cnt=0,tmp=0; int ans=0,ans_temp=0,k; void dfs(int i,int j) { // printf ("%d %d\n",i,j);if (mp[i][j]=='X'||vis[i][j]) return ;vis[i][j]=cnt;tmp++;dfs(i+1,j);dfs(i-1,j);dfs(i,j+1);dfs(i,j-1); } void add(int i,int j) {if (!vis[i][j])return ;int t=vis[i][j];if (!are_vis[t]) ans_temp+=are_num[t];are_vis[t]++; } void pop(int i,int j) {if (!vis[i][j])return ;int t=vis[i][j];are_vis[t]--;if (!are_vis[t]) ans_temp-=are_num[t]; } int clac(int x,int y){return sum[x+k-1][y+k-1]-sum[x+k-1][y-1]-sum[x-1][y+k-1]+sum[x-1][y-1]; } int main() {int n;scanf ("%d%d",&n,&k);memset(mp,'X',sizeof(mp));for (int i=1;i<=n;i++){scanf ("%s",mp[i]+1),mp[i][n+1]='X';}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){if (!vis[i][j]&&mp[i][j]=='.'){++cnt;tmp=0;dfs(i,j);are_num[cnt]=tmp;}}}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];if (mp[i][j]=='.') sum[i][j]++; // printf ("%d ",sum[i][j]); } // printf ("\n"); }for (int i=1;i<=n-k+1;i++){ans_temp=0;memset(are_vis,0,sizeof(are_vis));for (int x=i-1;x<=i+k;x++){for (int y=1;y<=k;y++){add(x,y); // printf ("加(%d %d)\n",x,y); // printf ("ans_temp==%d\n",ans_temp); }}for (int x=i;x<=i+k-1;x++)add(x,k+1); // printf ("加(%d %d)\n",x,k+1); // system("pause"); //printf ("%d\n",ans_temp);ans=max(ans,ans_temp+k*k-clac(i,1)); // cout<<"start"<<ans_temp+k*k-(sum[k+i-1][k]-sum[i-1][k])<<endl; // cout<<"zhong"<<sum[k+i-1][k]<<'-'<<sum[i-1][k]<<endl;for (int j=2;j+k-1<=n;j++){for (int x=i;x<=i+k-1;x++)pop(x,j-2),add(x,j+k); // printf ("-(%d,%d)\n",x,j-2),printf ("+(%d,%d)\n",x,j+k);pop(i-1,j-1);pop(i+k,j-1); // printf ("-(%d,%d)\n",i-1,j-1); // printf ("-(%d,%d)\n",i+k,j-1);add(i-1,j+k-1);add(i+k,j+k-1); // printf ("+(%d,%d)\n",i-1,j+k-1); // printf ("+(%d,%d)\n",i+k,j+k-1); // printf ("%d\n",ans_temp); // system("pause"); // cout<<"go"<<ans_temp+k*k-(sum[i+k-1][j+k-1]-sum[i+k-1][j-1]-sum[i-1][j+k-1]+sum[i-1][j-1])<<endl;ans=max(ans,ans_temp+k*k-clac(i,j));}}printf ("%d\n",ans); // for (int i=0;i<=n+1;i++) // { // for (int j=0;j<=n+1;j++) // { // printf ("%d",vis[i][j]); // } // printf ("\n"); // } // for (int i=1;i<=cnt;i++) printf ("%d ",are_num[i]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/nj-czy/p/5608077.html

總結(jié)

以上是生活随笔為你收集整理的codeforces 356C Bear and Square Grid的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。