专栏文章

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

TTiat_Siba_Ignareo
P13537题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mindwxfl
此快照首次捕获于
2025/12/02 00:49
3 个月前
此快照最后确认于
2025/12/02 00:49
3 个月前
查看原文
由于习惯，本文 nn 采用小写，即题目中的 NN。
很牛的题，在床上躺了半小时就想出来了 4n4n，但是 2n2n 真不好优化。
首先有：对于一个 r×cr \times c 的矩阵，如果 r>cr>c，r×rr \times r 的矩阵一定不劣；r<cr<c，c×cc \times c 的矩阵一定不劣。
可以构造性地扩展这个矩阵。方法很简单，就是不断放边上的数，举个例子，如果有以下矩阵：
PLAIN
1 2 3
1 2 3
2 2 2
3 2 1
可以这样改：
PLAIN
1 2 3 3
1 2 3 3
2 2 2 2
3 2 1 1
显然这不会改变国家与国家之间的接壤情况。至此就证明出来了。
所以放满一个 K×KK \times K 的矩阵一定不劣。既然这样，不妨就直接放满，更好写。
首先考虑最送的分，也就是链怎么做。那显然就是一个 n×nn \times n 的矩形，第 ii 行填满 ii。
但是这似乎并没有什么启示性。
完全图也是好做的。可以用类似循环位移的方式构造出来。但似乎也没有什么启示性。考虑国家 11 一定与其他所有国家相邻怎么做。显然有一个构造是：
PLAIN
1 1 1 1 1
2 * 2 * 2
1 1 1 1 1
* 表示其他的与 22 接壤的国家。类似这样，用 11 分隔其他国家，就构造完了。22 中间隔填其他国家，不妨称这个方法为 Swing 法。
然后考虑树怎么做。
可以发现，有这样的方法：
PLAIN
1 1 1 1 1
1 2 1 3 1
也就是，用父亲节点分隔各子树，递归拼成答案。这种方法不妨称为 Split-Brain 法。
然后，树会做了，思考一般的图怎么做。
很容易想到先求出来一棵生成树，这属于经典套路。
那这棵生成树，显然可以用 Split-Brain 法进行构造。
然后会发现，Split-Brain 法其实空出来了相当多的空间。
对于空出来的空间，完全可以使用 Swing 法去构造，来连上其他边。
最朴素的做法，当然是每个节点都把连了边的节点 Swing 法摊开来。掐指一算，刚好够过 N≤15N \leq 15。
现在前 4444 分被愉快地拿满了，来考虑后面的分怎么拿。
思考一下上面的暴力 Swing 摊开浪费在哪里。没错，就浪费在一条边实际被我们连了两次。此时又有了一个经典套路，让深度小的向深度大的连边，也就是 Split-Brain 法构造的时候，仅把深度更大的国家放进去。
如果不会这个经典套路，也能够发现越深的位置越挤。
现在需要计算这个构造的大小。
宽度没问题，是 2n−12n-1 的。高度呢？对不起，可以卡到略少于 3n3n。
所以还需要继续优化。
分析当前构造是什么样的。
PLAIN
1 1 1 1 1 1 1
1 * 1 * 1 * 1
1 1 1 1 1 1 1
2 2 2 1 3 3 3
2 * 2 1 3 * 3
2 2 2 1 3 3 3
是类似这样的形式，好像很浪费啊。浪费在哪呢？来看这个构造：
PLAIN
1 * 1 * 1 * 1
2 1 1 1 1 1 3
* 2 1 1 1 3 *
2 2 2 1 3 3 3
实际上是等价的。总结一下就是两点：
  1. 可以通过把角上的格子给其他国家用来节省空间。
  2. 第一行是没用的。
如果这样干，构造出来的矩阵是多大呢？刚好就是 (2n−1)×(2n−1)(2n-1) \times (2n-1)，完美。
然后会发现似乎不是很好实现。所以来说一下怎么实现。
首先，dfs 求生成树应该是没问题的。
然后先递归画出树的框架。对于一个生成树上，深度为 dd（为了方便从 00 开始）的国家，如果在宽上对应一个 [L,R][L,R] 的区间，那么：
  • 先从 (2d,L)(2d,L) 开始，从左到右隔一个填一个。
  • 从 (2d+1,L+1)(2d+1,L+1) 开始，从左到右隔一个填一个。
  • 如果不是根，从 (2d−1,L+1)(2d-1,L+1) 开始，从左到右隔一个填一个。
那就是类似于这样（. 和 * 表示空位，* 表示该国需要 Swing 方法填的接壤国，# 表示填了的）：
PLAIN
.#.#.#.#.
#*#*#*#*#
.#.#.#.#.
然后我们记录一下最左边 * 的位置，后面如果有要填的就填上，然后把位置往右跳两格。
然后递归着做。xx 个点的子树就是 2x−12x-1 的宽度，递归过去深度 +1+1。中间用当前国家分隔。刚好可以分出来。
然后就是剩下的空位怎么办。可以分为两种：
  1. 接壤国不够多，* 没填完。那就是找每个国家等待填接壤国的位置，如果不到该国家宽上所占范围的右端点就不断往右填。
  2. 其他的情况，根据这个构造方案，填和这一格上面一格一样的国家一定是对的。
然后就做完啦。
CPP
#include<bits/stdc++.h>
using namespace std;
vector<int> G[45], gtr[45];
vector< vector<int> > mp;
int fat[45], siz[45], dep[45], Rr[45];
pair<int, int> nxt[45];
bool vis[45];
void clr(int N){
	for (int i = 1; i <= N; i++){
		G[i].clear();
		gtr[i].clear();
		vis[i] = 0;
		fat[i] = siz[i] = dep[i] = 0;
	}
	mp.resize((N << 1) - 1);
	for (int i = 0; i < (N << 1) - 1; i++){
		mp[i].resize((N << 1) - 1);
	}
	for (int i = 0; i < (N << 1) - 1; i++)
		for (int j = 0; j < (N << 1) - 1; j++)
			mp[i][j] = 0;
}
void dfs(int u, int fa){
	vis[u] = 1;
	dep[u] = dep[fa] + 1;
	fat[u] = fa;
	++siz[u];
	for (auto v : G[u]){
		if (!vis[v]){
			gtr[u].emplace_back(v);
			dfs(v, u);
			siz[u] += siz[v];
		}
	}
}
void fil(int x, int y, int col){
	mp[x][y] = col;
}
void paint_tree(int u, int L, int R, int dep){
	Rr[u] = R;
	for (int i = L; i <= R; i += 2)
		fil(dep << 1, i, u);
	nxt[u] = make_pair(dep << 1, L + 1);
	for (int i = L + 1; i <= R; i += 2)
		fil(dep << 1 | 1, i, u);
	if (u != 1)
		for (int i = L + 1; i <= R; i += 2)
			fil((dep << 1) - 1, i, u);
	int nL = L;
	for (auto v : gtr[u]){
		++nL;
		int wid = (siz[v] << 1) - 1;
		paint_tree(v, nL, nL + wid - 1, dep + 1);
		nL = nL + wid;
	}
}
vector< vector<int> > create_map(int N, int M, vector<int> A, vector<int> B){
	clr(N);
	for (int i = 0; i < M; i++){
		G[A[i]].emplace_back(B[i]);
		G[B[i]].emplace_back(A[i]);
	}
	dfs(1, 0);
	paint_tree(1, 0, (N << 1) - 2, 0);
	for (int u = 1; u <= N; u++){
		for (auto v : G[u]){
			if (fat[v] != u && dep[v] > dep[u]){
				fil(nxt[u].first, nxt[u].second, v);
				nxt[u].second += 2;
			}
		}
	}
	for (int u = 1; u <= N; u++){
		while (nxt[u].second <= Rr[u] && !mp[nxt[u].first][nxt[u].second]){
			fil(nxt[u].first, nxt[u].second, u);
			nxt[u].second += 2;
		}
	}
	for (int i = 1; i < (N << 1) - 1; i++)
		for (int j = 0; j < (N << 1) - 1; j++){
			if (!mp[i][j])
				mp[i][j] = mp[i - 1][j];
		}
	return mp;
}
#ifndef ONLINE_JUDGE
int T, N, M;
vector<int> A, B;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> T;
	while (T--){
		cin >> N >> M;
		A.resize(M);
		B.resize(M);
		for (int i = 1; i <= M; i++){
			cin >> A[i - 1] >> B[i - 1];
		}
		vector< vector<int> > vec = create_map(N, M, A, B);
		cout << vec.size() << "\n";
		for (auto u : vec){
			for (auto v : u)
				cout << v << " ";
			cout << "\n";
		}
	}
	return 0;
}
#endif

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...