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

如果是树的话，其实很难想到直接欧拉序可以做到

2n

小一点，行数是

1

。~~但是我们可以做到更差！~~ 其实就是人类的思考过程：把每个子树包裹起来变成一个矩形。考虑归纳构造，构造一个子树的矩形，先把根放在最外层，然后把每个儿子的矩形依次放进去，中间用根隔开。例如：

CPP

其中 2 和 3 代表两棵儿子子树，

1

是根。

这样子的长度是

2n-1

，高度是树的深度。~~其实最后一行就是欧拉序。~~

考虑能不能取一个生成树，把剩下的边塞进去。既然是任意生成树那就取 dfs 树。很难想到可以把上面的结构弄松一点变成这样：

CPP

这样子就是每个子树的根处扩展成一个中空的包裹，可以用来塞点东西。这个包裹的大小大概是子树大小，所以对于每条返祖边，你把这条边深度大的点放到它祖先的包裹里即可。这样子高度是

3\times dep

，长度还是

2n-1

。可以获得

86

分的好成绩。

我们直观地感觉这个三层铺的有点浪费，观察一个例子：

CPP

11111111111
1?1?1?1?1?1
11111111111
12222222131
12?2?2?2131
12222222131
12444252131
124?4252131
12444252131
12464252131

其实可以发现对于相邻的两层（第

3a+b

行和第

3(a+1)+b

行，

b=1,2,3

），它们的 ? 的间隔开来的。对于如下左边的结构，其实可以变成右边：

CPP

111    1
1?1   1?1
111    1

节约掉四个角的空间之后，可以发现相邻两层解决掉的空间刚好是一奇一偶，正好可以岔开，所以上图就可以变成（只画前两层）：

CPP

1?1?1?1?1?1   1?1?1?1?1?1
11 1 1 1111   11212121111
1 2 2 2 131   12?2?2?2131
12?2?2?2131

这样每个深度就被压缩成了两层。顺便把第一行删掉。最后是

(2n-1)\times (2n-1)

。

CPP

#include "worldmap.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD         998244353
#define pii         pair<int,int>
#define all(v)      v.begin(),v.end()
#define pb          push_back
#define REP(i,b,e)  for(int i=(b);i<(int)(e);++i)
#define over(x)     {cout<<(x)<<endl;return;}
#define lowbit(x)   ((x)&(-(x)))
#define cntbit(x)   __builtin_popcount(x)
#define deal(v)     sort(all(v));v.erase(unique(v.begin(),v.end()),v.end())
#define lbound(v,x) lower_bound(all(v),x)-v.begin()
vector<vector<int>>ans;
vector<int>v[50],g[50];
int vis[50],fa[50],sz[50],dep[50];
void dfs(int x,int pre,int d){
	vis[x]=1;dep[x]=d;sz[x]=1;
	for(auto i:v[x])if(i!=pre){
		if(!vis[i]){
			fa[i]=x;
			g[x].pb(i);g[i].pb(x);
			dfs(i,x,d+1);
			sz[x]+=sz[i];
		}
	}
}
pii pos[50];
void color(int x,int pre,int l,int r,int d){
	REP(i,l,r+1)ans[d*2][i]=x;
	REP(i,l,r+1)if((i-l)&1){ans[d*2+1][i]=x;if(d)ans[d*2-1][i]=x;}
	pos[x]={d*2,l+1};
	for(auto i:g[x])if(i!=pre){
		++l;
		color(i,x,l,l+sz[i]*2-2,d+1);
		l+=sz[i]*2-1;
	}
}
vector<vector<int>>create_map(int n,int m,vector<int>U,vector<int>V){
	ans=vector<vector<int>>(n*2-1,vector<int>(n*2-1,0));
	REP(i,1,n+1)v[i].clear(),vis[i]=0,g[i].clear();
	REP(i,0,m)v[U[i]].pb(V[i]),v[V[i]].pb(U[i]);
	dfs(1,0,0);
	color(1,0,0,2*n-2,0);
	REP(i,1,n+1){
		for(auto j:v[i])if(dep[j]>dep[i]&&fa[j]!=i){
			auto &[x,y]=pos[i];
			ans[x][y]=j;
			y+=2;
		}
	}
	REP(i,0,n*2-1){
		REP(j,0,n*2-1)if(!ans[i][j]){
			if(i)ans[i][j]=ans[i-1][j];
			else ans[i][j]=ans[i][j-1];
		}
	}
	return ans;
}

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

文章操作

相关推荐

评论

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