COCI2021-2022 Contest2 T3

Tsawke · 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} ，其中：

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 映射到图上的任意节点，而不考虑树上的其他根节点的正确性很显然，对于任意一个节点作为根最终形成的结果应该是不变的，可以感性理解一下。

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

观察剩余的合法的解：

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

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

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

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

不难发现第一个可能的规律，将 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 初稿