自动搬运

查看原文

来自洛谷，原作者为

	Tsawke Never settle.

搬运于2025-08-24 22:34:44，当前版本为作者最后更新于2022-09-06 18:56:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

COCI2021-2022 Contest1 T3题解

[TOC]

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

原题面链接

Luogu题面

T3 Hiperkocka

题意

(这道题定义了一个 n-dimensional hipercube，但是实际上和这东西没什么关系)

存在一个 $2^n (n \le 16)$ 个节点的图，其中两个节点 $x, y$ 连通，当且仅当满足 $x \oplus y = 2^k \quad k \in \mathbb{N}$。

给定若干棵有 $n + 1$ 个节点 $n$ 条边的树，节点用 $0, 1, 2, \cdots, n$ 表示，要求将其放置在图中并对于每棵树都满足如下条件：

• 每棵树上每个节点都与图上节点一一对应。
• 每棵树上的每个节点对应的图上节点互不相同。
• 对于每棵树的边连结的两个节点，对应到图上之后，在图上两个节点仍然是联通的（即对应在图上两个节点的编号按位异或后的值为 $2$ 的整数次幂）。
• 图上的每条边只能对应一个树上的边。

需要你给定一种放置方案，使放置的树尽可能多。

采用 SPJ，可以证明最多能放 $2^{n - 1}$ 棵树，故采用如下方式计算得分：

若放置不合法则获得 $0 \texttt{pts}$，否则若正确放置了 $k$ 棵树，得分为 $f(k) \times 110 \texttt{pts}$，其中：

$$dp(l, r, k) = \left\{ \begin{array}{ll} 1 &\quad k = 2^{n - 1} \\ \dfrac{0.7k}{2^{n - 1}} &\quad k \lt 2^{n - 1} \end{array} \right. $$

Solution

本题的难度基本都在思维和找规律上，代码实现很简单，也并不需要用到任何高级算法和数据结构。

首先我们观察题目里一个很奇怪的条件，$x \oplus y = 2^k \quad k \in \mathbb{N}$，我们思考对于 $2^k$ 的二进制表达，显然有且仅有一个 $1$，而其他位置均为 $0$。我们在考虑运算的性质，异或运算得到 $1$ 的情况则需要两个数这一位置上不同。那么由此我们便不难发现，满足要求的 $x, y$ 在二进制上必须有且仅有一位不同。

通过这个性质我们可以进行一些大胆猜想：

假设我们只需要放置一棵树，那么可以考虑采用如下方案：

任意选择一个树上的节点作为根，并对应到图上的任意节点，这里我们考虑令树上的 $0$ 节点映射到图上的 $0$ 节点，记作 $0 \longrightarrow 0$。

对于树上剩余的点，我们考虑对其进行 DFS，按照其 DFS 序为其分配映射到图上的节点。

为了保证我们映射的节点不会重复，这里我们按照如下方案选点，对于 DFS 序等于 $\xi$ 的点，我们考虑使其父节点映射的图上节点对应的第 $\xi$ 位进行取反，可以通过对该位进行异或 $1$ 来实现。如果令父亲节点映射到图上的节点为 $\epsilon$ 则可以记作：$ \xi \longrightarrow \epsilon \oplus (1 \times 2^{\xi - 1}) $，或写成在搜索过程中写成 dfs(son, cur ^ (1 << (cur++)))。

现在我们就需要扩展到更多的树，注意题目有个要求即每条边只能用一次，那么就需要注意扩展的时候不能使用两次相同图上的父子关系（包括父子之间调换），这里我们可以尝试从一些较小的数找规律。

首先考虑若父亲为 $\epsilon$，其儿子为 $\xi$，则将父子关系记作 $\epsilon \rightarrow \xi$。

下面我们先找一种特殊情况，如 $n = 3$，树为一条 $0 \rightarrow 1 \rightarrow 2 \rightarrow 3$ 的链时，考虑每一种 $ 0 \longrightarrow i \quad i \in \left[ 0, 2^n - 1 \right] $（注意此时的 $\longrightarrow$ 为长箭头，指的是树与图之间的映射关系，而非父子关系，后文中也以此表示），会有如下可能性：

Tips：这里我们只考虑枚举以树上根节点为 $0$ 映射到图上的任意节点，而不考虑树上的其他根节点的正确性很显然，对于任意一个节点作为根最终形成的结果应该是不变的，可以感性理解一下。

$$\begin{aligned} i = 0: (000)_2 \rightarrow (001)_2 \rightarrow (011)_2 \rightarrow (111)_2 \\ i = 1: (001)_2 \rightarrow (000)_2 \rightarrow (010)_2 \rightarrow (110)_2 \\ i = 2: (010)_2 \rightarrow (011)_2 \rightarrow (001)_2 \rightarrow (101)_2 \\ i = 3: (011)_2 \rightarrow (010)_2 \rightarrow (000)_2 \rightarrow (100)_2 \\ i = 4: (100)_2 \rightarrow (101)_2 \rightarrow (111)_2 \rightarrow (011)_2 \\ i = 5: (101)_2 \rightarrow (100)_2 \rightarrow (110)_2 \rightarrow (010)_2 \\ i = 6: (110)_2 \rightarrow (111)_2 \rightarrow (101)_2 \rightarrow (001)_2 \\ i = 7: (111)_2 \rightarrow (110)_2 \rightarrow (100)_2 \rightarrow (000)_2 \end{aligned} $$

然后我们寻找不合法的解，如果我们贪心地优先保留 $i$ 更小的解，那么下面标注的这些部分显然是重复的不合法的：

$$\begin{aligned} i = 0: (000)_2 \rightarrow (001)_2 \rightarrow (011)_2 \rightarrow (111)_2 \\ i = 1: \underline{(001)_2 \rightarrow (000)_2} \rightarrow (010)_2 \rightarrow (110)_2 \\ i = 2: (010)_2 \rightarrow \underline{(011)_2 \rightarrow (001)_2} \rightarrow (101)_2 \\ i = 3: (011)_2 \rightarrow (010)_2 \rightarrow (000)_2 \rightarrow (100)_2 \\ i = 4: (100)_2 \rightarrow (101)_2 \rightarrow \underline{(111)_2 \rightarrow (011)_2} \\ i = 5: (101)_2 \rightarrow (100)_2 \rightarrow (110)_2 \rightarrow (010)_2 \\ i = 6: (110)_2 \rightarrow (111)_2 \rightarrow (101)_2 \rightarrow (001)_2 \\ i = 7: \underline{(111)_2 \rightarrow (110)_2} \rightarrow (100)_2 \rightarrow (000)_2 \end{aligned} $$

观察剩余的合法的解：

$$\begin{aligned} i = 0: (000)_2 \rightarrow (001)_2 \rightarrow (011)_2 \rightarrow (111)_2 \\ i = 3: (011)_2 \rightarrow (010)_2 \rightarrow (000)_2 \rightarrow (100)_2 \\ i = 5: (101)_2 \rightarrow (100)_2 \rightarrow (110)_2 \rightarrow (010)_2 \\ i = 6: (110)_2 \rightarrow (111)_2 \rightarrow (101)_2 \rightarrow (001)_2 \\ \end{aligned} $$

不难发现其符合一个规律，即二进制中 $1$ 的数量为偶数个（如果仍未发现可以考虑 $n = 4$ 的情况）。

经过验证，显然当树的形态不为一条链的时候该结论仍然成立。

下面我们需要思考如何计算这些扩展出来的节点，显然我们可以每次都进行一次 $\texttt{DFS}$，时间复杂度大约是 $O(n2^n)$，显然可以接受，于是这题就切了...不过我们可以考虑接着找规律（虽然并不能优化复杂度）。

观察刚才得到的合法解中的每一列：

$$\begin{aligned} i = 0: (000)_2 \rightarrow (001)_2 \rightarrow (011)_2 \rightarrow (111)_2 \\ i = 3: (011)_2 \rightarrow (010)_2 \rightarrow (000)_2 \rightarrow (100)_2 \\ i = 5: (101)_2 \rightarrow (100)_2 \rightarrow (110)_2 \rightarrow (010)_2 \\ i = 6: (110)_2 \rightarrow (111)_2 \rightarrow (101)_2 \rightarrow (001)_2 \\ \end{aligned} $$

不难发现第一个可能的规律，将 $i = 0$ 的情况中每一个数的第 $k$ 位保留不变并将其他位全部取反，枚举 $k$ 便可以得到剩余的情况。但是这真的正确吗？我们可以考虑随意构造一个非链状的树，简单验证后就会发现这个规律假掉了（这里就不写验证过程了，很简单）。

于是我们继续尝试构造规律，可以发现若对于每一个符合要求的 $i (i \neq 0)$ 与 $i = 0$ 时的每一个数进行异或运算后，得到的结果便是一组新的解，并且经过验证这个规律在其他树的形态仍然是正确的。

至此我们便可以考虑用 dp 思想，$O(2^n)$ 预处理出所有合法的 $i$，然后按照我们的算法进行计算，时间复杂度大概是 $O(n2^n)$，可以接受。

同时建议对于这种规律题如果有时间，打个对拍验证一下规律的正确性。

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr

using namespace std;

mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;

template<typename T = int>
inline T read(void);

vector < int > vert[110000];
int N;
int base[110000];
bool vis[110000];
int cur(0);
void dfs(int p, int mapp){
    base[p] = mapp;
    vis[p] = true;
    for(auto i : vert[p]){
        if(!vis[i]){
            vis[i] = true;
            dfs(i, mapp ^ (1 << (cur++)));
        }
    }
}
int dp[110000];
vector < int > legal;
void Init(int N){
    int lim = 1 << N;
    dp[0] = 0;
    for(int i = 1; i <= lim; ++i){
        dp[i] = dp[i >> 1] + (i & 1);
        if(!(dp[i] & 1))legal.push_back(i);
    }
}
int main(){
    N = read();
    for(int i = 1; i <= N; ++i){
        int f = read(), t = read();
        vert[f].push_back(t);
        vert[t].push_back(f);
    }
    dfs(0, 0);
    Init(N);
    printf("%d\n", (int)legal.size() + 1);
    for(int i = 0; i <= N; ++i)printf("%d%c", base[i], i == N ? '\n' : ' ');
    for(auto i : legal)
        for(int j = 0; j <= N; ++j)
            printf("%d%c", base[j] ^ i, j == N ? '\n' : ' ');
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

2022_09_05 完成 T1 - T3 及 T4 一部分

2022_09_06 初稿