题解：P7966 [COCI 2021/2022 #2] Hiperkocka

首先相信大家都发现了得满分要求每条边都被选入某棵树。

从菊花入手，此时等价于选出

2^{n-1}

个数使得他们两两之间相差至少两个二进制位。只需要选出所有

\mathrm{popcount}

为偶数的数即可。

再考虑一般情况，换个角度理解题意，就是对于每条边

(x,y)

能找出它是哪棵树的哪条边。

尝试将这个定位逻辑简单化，那么由

x

和

y

得出的一个简单信息是

x

与

y

在哪一位不同，设为

i

，那么我们可以规定它被定位到某棵树的第

i

条边上。

这也就是给

T

的每条边赋一个互不相同的

0

至

n-1

的边权（顺序随意），要求结果中每个

T

的相邻两点间相差的位就是边上的边权，即对于每个

1\le i\le 2^{n-1}

有

\forall u,v,(u,v)\in T: a_{i,u}\oplus a_{i,v}=2^{e_(u,v)}

，其中

e

为所赋的边权。

于是此时我们只用确定

a_{i,0}

整个

a_i

序列就确定了。只需考虑怎么给每个

a_{i,0}

赋值。

考虑什么时候两棵树的两条边会冲突。

那么若

T_1

和

T_2

都含有边

(x,y)

，则

(x,y)

在

T_1

和

T_2

的边权必然相同（为

\log_2(x\oplus y)

），也即它们是

T

上的同一条边。

我们将树按从根向叶子的方向定向，则若

(x,y)

在

T_1

和

T_2

中的方向相同，可以倒推出

T_1

和

T_2

的根节点权值相同，矛盾。

因此只有当

(x,y)

在

T_1

中是

x\rightarrow y

而在

T_2

中是

y\rightarrow x

时有可能冲突，此时可以推出

T_1

和

T_2

的根节点的权值恰相差一个二进制位

e_{(x,y)}

。

rt_1 \xrightarrow{c_1} \ \xrightarrow{c_2} \dots \xrightarrow{c_m} x \xleftrightarrow{e_{(x,y)}} y \ \xleftarrow{c_m} \dots \xleftarrow{c_2} \ \xleftarrow{c_1} rt_2

于是沿用菊花的做法，令每个根的节点都是

\mathrm{popcount}

为偶数的数即可。

代码 500B。

CPP

#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
constexpr int N=55;
int n,a[N],cnt; vector<int> to[N];
void dfs(int u,int pa) { for(int v:to[u]) if(v!=pa) a[v]=a[u]^(1<<(cnt++)), dfs(v,u); }
int main(){
    cin>>n; For(i,1,n) { int x,y; cin>>x>>y; to[x].push_back(y); to[y].push_back(x); }
    dfs(0,-1); cout<<(1<<(n-1))<<'\n';
    For(s,0,(1<<n)-1) if(__builtin_parity(s)) For(i,0,n) cout<<(s^a[i])<<" \n"[i==n];
    return 0;
}

题解：P7966 [COCI 2021/2022 #2] Hiperkocka

文章操作

相关推荐

评论

题解：P7966 [COCI 2021/2022 #2] Hiperkocka