2023NOIP A层联测17

联测17"/>

2023NOIP A层联测17

给出一个 n × m n×m n×m 的网格图，其中一些格子上有一个炸弹，一些格子上有一个水晶，剩下的格子为空地，什么也没有。

炸弹可以被引爆。每当一个炸弹被引爆，它必须选择：引爆它所在的这一行或者引爆它所在的这一列。水晶被引爆后会消失（即如果一个水晶所在的行列均被引爆，也只计算一次），炸弹被引爆后，会产生连锁反应，被引爆的炸弹也会选择引爆它所在的行或者列，如此下去直到没有新的炸弹被引爆。

现在你可以选择一个炸弹和其引爆的方向，请你求出最多可以引爆多少个水晶。

n , m ≤ 3000 n,m\le3000 n,m≤3000

当一个炸弹以一个方向被引爆时，被触发的炸弹引爆方向是相反的。显然这是最佳的。

考虑对每个炸弹的上下左右离它最近的炸弹连边。这样就形成了若干个连通块，互不影响，可以分别计算答案。

若一个连通块内有环，那么任意引爆其中一个炸弹，整个连通块的炸弹都会被引爆，得到连通块涉及的行列的水晶。

若没有环，就可以选择一个只有左右/上下有炸弹的炸弹，将其引爆，这样可以把连通块内所有炸弹引爆，对比上一个情况的水晶，容易发现少了某一列/行的水晶（建议自己手模一下），减去即可。

时间复杂度 O ( n m ) O(nm) O(nm)。

具体实现看代码

#include<bits/stdc++.h>
using namespace std;
const int N=3001,NN=9000001;
int n,m,num1,num2,ans,vis[NN],dfn[NN],low[NN],num,fl,d[NN];
char a[N][N];
int head[NN],nxt[NN<<2],to[NN<<2],cnt,w[NN<<2];
vector<int> v1,v2,v3;
unordered_map<int,int> m1,m2; 
void add(int u,int v,int W)
{to[++cnt]=v;w[cnt]=W;nxt[cnt]=head[u];head[u]=cnt;
}
int ID(int x,int y){return (x-1)*m+y;}
pair<int,int> DI(int x){return make_pair((x-1)/m+1,(x-1)%m+1);}
void dfs(int u,int fa)
{v3.push_back(u);auto czn=DI(u);vis[u]=1;if(!m1.count(czn.first)) m1[czn.first]=1,v1.push_back(czn.first);if(!m2.count(czn.second)) m2[czn.second]=1,v2.push_back(czn.second);for(int i=head[u];i;i=nxt[i]){if(to[i]!=fa){if(vis[to[i]]){fl=1;continue;}dfs(to[i],u);}}
}
bool check(int x)
{int x1=0,x2=0;for(int i=head[x];i;i=nxt[i]){if(w[i]) x1=1;else x2=1;}return x1^x2;
}
int main()
{freopen("boom.in","r",stdin);freopen("boom.out","w",stdout);scanf("%d%d%d%d",&n,&m,&num1,&num2);for(int i=1;i<=n;i++) scanf("%s",a[i]+1);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]!='b') continue;int x=i+1,y=j;while(x<=n&&a[x][y]!='b') x++;if(x<=n){add(ID(i,j),ID(x,y),1),add(ID(x,y),ID(i,j),1);d[ID(i,j)]++,d[ID(x,y)]++;}x=i,y=j+1;while(y<=m&&a[x][y]!='b') y++;if(y<=m){add(ID(i,j),ID(x,y),0),add(ID(x,y),ID(i,j),0);d[ID(i,j)]++,d[ID(x,y)]++;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!vis[ID(i,j)]&&a[i][j]=='b'){fl=0;v1.clear(),v2.clear(),v3.clear();m1.clear(),m2.clear();dfs(ID(i,j),0);sort(v1.begin(),v1.end());sort(v2.begin(),v2.end());int sum=0;for(auto i:v1) for(int j=1;j<=m;j++) sum+=(a[i][j]=='k');for(int i=1;i<=n;i++) for(auto j:v2) sum+=(a[i][j]=='k');for(auto i:v1) for(auto j:v2) sum-=(a[i][j]=='k');if(fl){ans=max(ans,sum);}else{for(auto i:v3){if(check(i)){auto czn=DI(i);int x=sum;if(w[head[i]]){for(int j=1;j<=m;j++) x-=(a[czn.first][j]=='k');for(auto j:v2) x+=(a[czn.first][j]=='k');}else{for(int i=1;i<=n;i++) x-=(a[i][czn.second]=='k');for(auto i:v1) x+=(a[i][czn.second]=='k');}ans=max(ans,x);}}if(d[ID(i,j)]==0){auto czn=DI(ID(i,j));int x=sum;for(int j=1;j<=m;j++) x-=(a[czn.first][j]=='k');for(auto j:v2) x+=(a[czn.first][j]=='k');ans=max(ans,x);x=sum;for(int i=1;i<=n;i++) x-=(a[i][czn.second]=='k');for(auto i:v1) x+=(a[i][czn.second]=='k');ans=max(ans,x);}}}}}cout<<ans;
}