这道题并查集部分求教
  • 板块P3940 分组
  • 楼主hbhz_zcy
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/9/6 15:33
  • 上次更新2023/10/27 12:24:52
查看原帖
这道题并查集部分求教
142549
hbhz_zcy楼主2022/9/6 15:33

rt,76pts,最后几个点没有过。
我觉得应该是并查集部分打挂了。
尝试过重构,无效。
尝试过对拍,数据小于1000根本拍不出来。
主体:

for(int i=N;i;i--){
	int flag=0;
	for(int j=maxb;pre[j]>a[i];j--)  if(tn[pre[j]-a[i]]&&(flag|=mg(a[i],pre[j]-a[i])))  break;
	if(flag){
		for(int j=f[ftop];j>i;j--)  tn[a[j]]=vis[a[j]]=0,b[a[j]]=a[j],b[a[j]+maxm]=a[j]+maxm;
		f[++ftop]=i;
	}
	tn[a[i]]++;
}

merge函数:

bool mg(int x,int y){
	if(x==y)  vis[x]+=2;
	else vis[x]|=1,vis[y]|=1,b[fa(x)]=fa(y+maxm),b[fa(y)]=fa(x+maxm);
	return vis[x]>2||vis[y]>2||fa(x)==fa(x+maxm)||fa(y)==fa(y+maxm);
}

意思大概是说,判一次重复自己会导致自己再也不能进入判定,然后交错连边,最后判重。

2022/9/6 15:33
加载中...