社区讨论
悬关,WA on 6,求助大佬
CF1985H2 Maximize the Largest Component (Hard Version)参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m5oxpe6h
- 此快照首次捕获于
- 2025/01/09 14:15 去年
- 此快照最后确认于
- 2025/01/09 21:00 去年
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
int t,n,m,fa[N],dx[5]={1,0,-1,0},dy[5]={0,1,0,-1},sz[N],ans,a[N],d[N];
int nor[N],wes[N],eas[N],sou[N],hang[N],lie[N];
char c[N];
bool vis[N];
int change(int x,int y){
return (x-1)*m+y;
}
bool check(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m&&c[change(x,y)]=='#';
}
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void merge(int u,int v){
u=find(u),v=find(v);
if(u==v)return ;
nor[v]=min(nor[v],nor[u]),sou[v]=max(sou[v],sou[u]),wes[v]=min(wes[v],wes[u]),eas[v]=max(eas[v],eas[u]);
fa[u]=v,sz[v]+=sz[u];
}
void init(int sx,int tx,int sy,int ty,int sum){
d[change(sx,sy)]+=sum,d[change(tx+1,sy)]-=sum,d[change(sx,ty+1)]-=sum,d[change(tx+1,ty+1)]+=sum;
}
//没有问题
signed main () {
cin>>t;
while(t--){
scanf("%lld%lld",&n,&m);
ans=0;
for(int i=1;i<=max(n,m);i++)hang[i]=0,lie[i]=0;
for(int i=1;i<=n*m;i++){
fa[i]=i,vis[i]=0,sz[i]=1,d[i]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
nor[change(i,j)]=sou[change(i,j)]=i;
wes[change(i,j)]=eas[change(i,j)]=j;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)cin>>c[change(i,j)];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(c[change(i,j)]=='.'){
hang[i]++,lie[j]++;
continue;
}
for(int k=0;k<4;k++){
int nx=i+dx[k];
int ny=j+dy[k];
if(check(nx,ny))merge(change(i,j),change(nx,ny));
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int pos=(i-1)*m+j;
if(c[pos]=='#'){
pos=find(pos);
if(vis[pos])continue;
vis[pos]=1;
nor[pos]=max(1ll,nor[pos]-1),sou[pos]=min(n,sou[pos]+1);
wes[pos]=max(1ll,wes[pos]-1),eas[pos]=min(m,eas[pos]+1);
init(1,nor[pos]-1,wes[pos],eas[pos],sz[pos]);
init(nor[pos],sou[pos],1,m,sz[pos]);
init(sou[pos]+1,n,wes[pos],eas[pos],sz[pos]);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
d[change(i,j)]+=d[change(i-1,j)]+d[change(i,j-1)]-d[change(i-1,j-1)];
ans=max(ans,d[change(i,j)]+hang[i]+lie[j]-(c[change(i,j)]=='.'));
}
}
printf("%lld\n",ans);
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...