社区讨论

悬关,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 条回复,欢迎继续交流。

正在加载回复...