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

Tiat_Siba_Ignareo · 2025-11-04 11:47:30 · 题解

由于习惯，本文 n 采用小写，即题目中的 N。

很牛的题，在床上躺了半小时就想出来了 4n，但是 2n 真不好优化。

首先有：对于一个 r \times c 的矩阵，如果 r>c，r \times r 的矩阵一定不劣；r<c，c \times c 的矩阵一定不劣。

可以构造性地扩展这个矩阵。方法很简单，就是不断放边上的数，举个例子，如果有以下矩阵：

可以这样改：

显然这不会改变国家与国家之间的接壤情况。至此就证明出来了。

所以放满一个 K \times K 的矩阵一定不劣。既然这样，不妨就直接放满，更好写。

首先考虑最送的分，也就是链怎么做。那显然就是一个 n \times n 的矩形，第 i 行填满 i。

但是这似乎并没有什么启示性。

完全图也是好做的。可以用类似循环位移的方式构造出来。但似乎也没有什么启示性。考虑国家 1 一定与其他所有国家相邻怎么做。显然有一个构造是：

1 1 1 1 1
2 * 2 * 2
1 1 1 1 1

* 表示其他的与 2 接壤的国家。类似这样，用 1 分隔其他国家，就构造完了。2 中间隔填其他国家，不妨称这个方法为 Swing 法。

然后考虑树怎么做。

可以发现，有这样的方法：

1 1 1 1 1
1 2 1 3 1

也就是，用父亲节点分隔各子树，递归拼成答案。这种方法不妨称为 Split-Brain 法。

然后，树会做了，思考一般的图怎么做。

很容易想到先求出来一棵生成树，这属于经典套路。

那这棵生成树，显然可以用 Split-Brain 法进行构造。

然后会发现，Split-Brain 法其实空出来了相当多的空间。

对于空出来的空间，完全可以使用 Swing 法去构造，来连上其他边。

最朴素的做法，当然是每个节点都把连了边的节点 Swing 法摊开来。掐指一算，刚好够过 N \leq 15。

现在前 44 分被愉快地拿满了，来考虑后面的分怎么拿。

思考一下上面的暴力 Swing 摊开浪费在哪里。没错，就浪费在一条边实际被我们连了两次。此时又有了一个经典套路，让深度小的向深度大的连边，也就是 Split-Brain 法构造的时候，仅把深度更大的国家放进去。

如果不会这个经典套路，也能够发现越深的位置越挤。

现在需要计算这个构造的大小。

宽度没问题，是 2n-1 的。高度呢？对不起，可以卡到略少于 3n。

所以还需要继续优化。

分析当前构造是什么样的。

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

是类似这样的形式，好像很浪费啊。浪费在哪呢？来看这个构造：

1 * 1 * 1 * 1
2 1 1 1 1 1 3
* 2 1 1 1 3 *
2 2 2 1 3 3 3

实际上是等价的。总结一下就是两点：

可以通过把角上的格子给其他国家用来节省空间。
第一行是没用的。

如果这样干，构造出来的矩阵是多大呢？刚好就是 (2n-1) \times (2n-1)，完美。

然后会发现似乎不是很好实现。所以来说一下怎么实现。

首先，dfs 求生成树应该是没问题的。

然后先递归画出树的框架。对于一个生成树上，深度为 d（为了方便从 0 开始）的国家，如果在宽上对应一个 [L,R] 的区间，那么：

先从 (2d,L) 开始，从左到右隔一个填一个。
从 (2d+1,L+1) 开始，从左到右隔一个填一个。
如果不是根，从 (2d-1,L+1) 开始，从左到右隔一个填一个。

那就是类似于这样（. 和 * 表示空位，* 表示该国需要 Swing 方法填的接壤国，# 表示填了的）：

.#.#.#.#.
#*#*#*#*#
.#.#.#.#.

然后我们记录一下最左边 * 的位置，后面如果有要填的就填上，然后把位置往右跳两格。

然后递归着做。x 个点的子树就是 2x-1 的宽度，递归过去深度 +1。中间用当前国家分隔。刚好可以分出来。

然后就是剩下的空位怎么办。可以分为两种：

接壤国不够多，* 没填完。那就是找每个国家等待填接壤国的位置，如果不到该国家宽上所占范围的右端点就不断往右填。
其他的情况，根据这个构造方案，填和这一格上面一格一样的国家一定是对的。

然后就做完啦。

#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