题解：P13537 [IOI 2025] 世界地图 worldmap

72 \rm pts

是整个题的最基本思路，也就是构建一个

4n\times 2n

（为了形成正方形其实是

4n\times 4n

）。

这部分的构造就是先考虑树，很容易按照子树来分类，使用父亲来间隔各个儿子，然后递归处理儿子进行就行了。

CPP

u v1 u v2 u 
u v1 u v2 u
u v1 u v2 u

扩展到一般图，同理考虑 dfs 树，会产生返祖边。我们可以单独开一列表示一些能上来的孙子节点，中间用

u

来隔开。这么做是

4n\times 2n

的。

CPP

u v1 u v2 u c1 u
u v1 u v2 u u  u
u v1 u v2 u c2 u

其实信息量是

8n^2<3n\times 3n

，但是为了凑成正方形不得不变成

4n\times 4n

。所以考虑均匀分布，返祖边信息还是竖着来，这个时候我们发现儿子信息其实可以并列地放在若干行内。原因是行的高度约束是

2\times

子树大小，而儿子子树大小求和刚好是父亲子树大小量级，所以你可以这么塞进去。这么做的意义是我们把原先列之间的

u

间隔放到了行中，减少了列数。这么做是

3n\times 2n

的，有

86\rm pts

。

CPP

u u  u u  u
u c1 u v1 v1
u u  u u  u
u c2 u v1 v1
u u  u u  u

略加优化就可以满分了，你会发现下图中的问号位置并不需要填入

u

，于是你在相邻两层镶嵌插入就可以减少一个

n

的宽度了。

CPP

? u  ? u  u
u c1 u v1 v1
? u  u u  u
u c2 u v1 v1
? u  ? u  u

CPP

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=300;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int n,m,dfn[maxn],e[maxn][maxn],sz[maxn],rev[maxn]; 
vector<int> G[maxn],son[maxn]; int tot=0;
vector<vi> emp,ans;
void Clear(){
	for(int i=1;i<=n;i++){
		G[i].clear(); son[i].clear();
		dfn[i]=sz[i]=rev[i]=0;
		for(int j=1;j<=n;j++) e[i][j]=0;
	} tot=0;
}
void dfs(int u){
	sz[u]=1; dfn[u]=++tot; rev[tot]=u;
	for(auto v:G[u]){
		if(dfn[v]) continue;
		dfs(v); sz[u]+=sz[v];
		son[u].pb(v);
	}
}
vi merge(vi L,vi R){ for(auto z:R) L.pb(z); return L; }
vector<vi> solve(int u,int len){
	if(!son[u].size()) return emp;
	vector<vi> res,cur; vi s,tt(1,u);
	for(int i=dfn[u]+1;i<=dfn[u]+sz[u]-1;i++){
		int v=rev[i];
		if(e[u][v]) s.pb(v);
	}
	res.resize(2*s.size());
	if(u==1) for(auto &z:res) z.pb(u);
	for(int i=0;i<s.size();i++){//交替放置 u s[i] 
		res[2*i].pb(u);
		res[2*i+1].pb(s[i]);
	}
	for(auto &z:res)
		if(z.back()!=u) z.pb(u);//外层封住 s[i] 
	int j=1,flag=0;//第一行空着 
	if(u==1) tt.pb(u);
	for(auto v:son[u]){
		cur=solve(v,len-2-(u==1));
		if(!cur.size()) continue;
		flag=1;
		while(j+cur.size()+1>res.size()) res.pb(tt);
		if(res[j+1].size()>=2+(u==1)) j++;
		for(auto z:cur){
			if(res[j].size()<2+(u==1)) res[j].pb(v);
			res[j]=merge(res[j],z); j++;
		}
		res[j++].pb(u);
	}
	flag=1;
	for(auto id:res.back())
		if(id!=u) flag=0;
	if(!flag) res.pb(tt);//封底 
	for(auto &z:res)//补满
		while(z.size()<len) z.pb(z.back());	
	return res;
}
vector<vi> create_map(int N,int M,vi A,vi B){
	n=N; m=M; ans.clear();
	if(n==1){
		vi tmp; tmp.pb(1);
		ans.pb(tmp); return ans;
	}
	for(int i=0;i<m;i++){
		e[A[i]][B[i]]=e[B[i]][A[i]]=1;
		G[A[i]].pb(B[i]),G[B[i]].pb(A[i]);
	}
	dfs(1); ans=solve(1,2*n);
	vi base=ans.back();
	while(ans.size()<2*n) ans.pb(base);
	Clear(); return ans;
}

题解：P13537 [IOI 2025] 世界地图 worldmap

文章操作

相关推荐

评论

题解：P13537 [IOI 2025] 世界地图 worldmap