自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 21:38:18，当前版本为作者最后更新于2024-04-12 22:05:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

连通性问题自然考虑插头 DP。

先有个简单的想法，按照输入顺序依次加入三角形，每次记录还有边没被考虑过的三角形的连通情况，最多 $2n$ 个，按照最小字典序标号，$3$ 个起点的连通块单独记录，为了统计答案，将 $3$ 个终点的连通情况也记录下来。

可以用 $16$ 进制数来表示状态，但是这样总状态数太多了。

考虑到我们记录了所有树的状态，但实际上我们只要记录链的状态。

考虑记录每条链的端点，链中间的点用 $0$ 来表示。

注意到最优解起点和终点会恰好连 $1$ 条边，其余点连 $0$ 或 $2$ 条边，所以我们要在连边时保证这个条件，不然状态数还是会超。

发现考虑到第 $i$ 个点时，连通块连出去的边，只有 $i$ 和 $i+1$ 这条是横向边，其余边都是纵向边。

所以我们可以在之前的状态中，单独记录 $i$ 和 $i+1$ 这条边选不选，这样我们就能保证每个点只连 $0$ 或 $2$ 条边。

保证了之后状态数就不多了，可以通过。

上述方法仅供参考，可能存在更简洁的表示方法。

参考代码加了一些可有可无的剪枝，可读性可能较差。

参考代码（主体部分）：

typedef unsigned long long ull;
typedef pair<int,int> pii;
const int N=225,P=1e9+7,Hs=3e6+17,M=1e6+5;
int n,m,a[N],ln[25],vis[4],mx[N],nw,ls,co[N],fa[25],nc[25],sz[25],l1,l2,e[N],E[N];
vector<int>p[N];
pii w[M][2];
int hd[Hs][2],num[2],nx[M][2];
ull to[M][2];
bool vs[25],lc[N],g[N];
inline int md(int x){
	return x>=P?x-P:x;
}
inline pii operator +(pii a,pii b){
	pii c;
	c.first=min(a.first,b.first),c.second=0;
	if(a.first==c.first)c.second=md(c.second+a.second);
	if(b.first==c.first)c.second=md(c.second+b.second);
	return c;
}
void add(int x,int y){
	if(a[x]==4||a[y]==4)return;
	if(x!=y+1)e[x]=y,E[y]=x;
	else g[x]=true;
	mx[y]=max(mx[y],x);
}
inline void ins(ull S,pii v){
	int o=S%Hs;
	for(int i=hd[o][nw];i;i=nx[i][nw])if(to[i][nw]==S){
		w[i][nw]=w[i][nw]+v;
		return;
	}
	nx[++num[nw]][nw]=hd[o][nw],hd[o][nw]=num[nw];
	to[num[nw]][nw]=S,w[num[nw]][nw]=v;
}
inline void chg(int id,ull S,pii v,int o,int e0=0,int e1=0){
	S>>=1;
	v.first+=(e0>0)+(e1>0);
	for(int i=1;i<=12;++i)fa[i]=i,vs[i]=false,sz[i]=0;
	for(int i=0;i<l1;++i)co[p[id-1][i]]=S>>(4*i)&15,++sz[co[p[id-1][i]]];
	if(e[id]&&co[e[id]]&&!lc[e[id]]&&e0!=e[id]&&e1!=e[id])return;
	int &c=co[id];
	c=12;
	if(a[id]&&!vis[a[id]])c=a[id];
	++sz[c];
	if(!a[id]&&!o&&!e0)c=0;
	if(e0&&!e1){
		int &u=co[e0];
		if(!u)return;
		if(c<4){
			fa[u]=c,c=0;
			if(sz[u]>1)u=0;
		}else{
			c=u;
			if(u<4||sz[u]>1)u=0;
		}
	}else if(e1){
		if(co[e0]>co[e1])swap(e0,e1);
		int &x=co[e0],&y=co[e1];
		co[id]=0;
		if(!x||x==y)return;
		if(y<4)return;
		fa[y]=x;
		if(x<4){
			x=0;
			if(sz[y]>1)y=0;
		}else{
			if(sz[x]>1)x=0;
			if(sz[y]>1)y=0;
		}
	}
	for(int i=0;i<l2;++i){
		int t=p[id][i],c=co[t];
		if(!lc[t])continue;
		if(!c)return;
		if(fa[c]<4&&fa[c]!=a[t])return;
		if(mx[t]<=id&&fa[c]!=a[t]){
			bool fg=false;
			if(id==m)return;
			for(auto z:p[id])if(!lc[z]&&fa[co[z]]==fa[co[t]]){
				fg=true;
				break;
			}
			if(!fg)return;
		}
	}
	ull T=0;
	for(int i=0,ct=4;i<l2;++i){
		int t=p[id][i];
		if(!co[t])continue;
		int u=fa[co[t]];
		if(u<4){
			T|=ull(u)<<(i*4);
			vs[u]=true;
			continue;
		}
		if(!vs[u])vs[u]=true,nc[u]=ct++;
		T|=ull(nc[u])<<(i*4);
	}
	for(int i=1;i<4;++i)if(vis[i]==1&&!vs[i])return;
	ins(T<<1|o,v);
}
void solve(){
	m=6*n*n,num[0]=num[1]=0;
	memset(vis,false,sizeof(vis));
	memset(hd,0,sizeof(hd));
	for(int i=1;i<=m;++i)e[i]=g[i]=E[i]=mx[i]=lc[i]=0;
	for(int i=1;i<=2*n;++i){
		if(i<=n)ln[i]=2*n+2*i-1;
		else ln[i]=2*n+2*(2*n-i)+1;
	}
	for(int i=1,id=0;i<=2*n;++i){
		for(int j=1;j<=ln[i];++j){
			++id;
			scanf("%d",&a[id]);
			if(a[id]&&a[id]!=4){
				if(vis[a[id]])lc[id]=true;
				vis[a[id]]=true;
			}
			if(j>1)add(id,id-1);
			if((i<=n)!=(j&1)){
				if(i>1){
					if(i<=n)add(id,id-ln[i]+1);
					if(i==n+1)add(id,id-ln[i]);
					if(i>n+1)add(id,id-ln[i]-1);
				}
			}
		}
	}
	for(int i=0;i<=m;++i){
		p[i].clear();
		for(int j=1;j<=i;++j)if(mx[j]>i||lc[j])p[i].push_back(j);
	}
	memset(vis,false,sizeof(vis));
	nw=0,ls=1;
	ins(0,{0,1});
	for(int i=1;i<=m;++i){
		l1=p[i-1].size(),l2=p[i].size();
		swap(nw,ls),num[nw]=0;
		if(a[i]==4)a[i]=0;
		for(int j=1;j<=num[ls];++j){
			ull S=to[j][ls];pii v=w[j][ls];
			hd[S%Hs][ls]=0;
			if(!(S&1)){
				if(a[i]){
					if(g[i+1])chg(i,S,v,1);
					if(e[i])chg(i,S,v,0,e[i]);
					if(E[i])chg(i,S,v,0);
				}else{
					chg(i,S,v,0);
					if(g[i+1]&&e[i])chg(i,S,v,1,e[i]);
					if(g[i+1]&&E[i])chg(i,S,v,1);
				}
			}else{
				if(a[i]){
					chg(i,S,v,0,i-1);
				}else{
					if(g[i+1])chg(i,S,v,1,i-1);
					if(e[i])chg(i,S,v,0,i-1,e[i]);
					if(E[i])chg(i,S,v,0,i-1);
				}
			}
		}
		++vis[a[i]];
	}
	if(!num[nw]){
		puts("-1 -1");
		return;
	}
	pii ans={100000,0};
	for(int i=1;i<=num[nw];++i)ans=ans+w[i][nw];
	printf("%d %d\n",ans.first,ans.second);
}