高阶扩展：掩码图上的欧拉回路

本节目标

从“最大化相邻连接的二进制低位相等数”推导出答案单调性，再把固定物件看成边、可粘合颜色看成点，用欧拉回路同时完成判定与构造。

前置知识与课前自测

前置：无向欧拉回路、Hierholzer、位运算。

两数 XOR 能被 $2^k$ 整除等价于哪 $k$ 位相同？
若每个物件必须整体使用且可翻转，为什么它更像边而不是点？
无向多重图存在覆盖全部边的欧拉回路需要什么条件？

答案

1. 最低 $k$ 位。 2. 物件有两个可交换端点，使用一次正好对应沿一条无向边走一次。 3. 所有非零度点连通且度数为偶数。

问题动机：先固定目标值

若直接排列 $n$ 个链节并决定每个链节朝向，搜索空间包含排列与 $2^n$ 次翻转。真正可利用的不是“美丽值”的数值，而是阈值判定：要求每次粘合美丽值至少为 $k$，等价于粘合的两种颜色最低 $k$ 位相同。

随着 $k$ 增大，条件只会变严。因此先解决“给定 $k$ 能否构造”，再从 20 向下找第一个可行值。

精选例题：Johnny and Megan's Necklace

来源与题意

VJudge：CodeForces-1361C
原题：Codeforces 1361C
难度：2500；考点：二进制阈值、掩码多重图、欧拉构造

有 $n\le5\times10^5$ 个链节，第 $i$ 个两端颜色为 $a_i,b_i<2^{20}$。链节可翻转，并把所有端点两两粘合成一个环。一次粘合的美丽值是 $a\oplus b$ 的二进制末尾零数（相等时为 20）；最大化所有粘合中的最小值，并输出链上 $2n$ 个原端点编号顺序。

Hint 1

固定 $k$ 后只保留颜色 `color & ((1<<k)-1)`。

Hint 2

一个链节连接两个掩码，应成为无向多重图的一条边。

Hint 3

链节内部对应走过一条边；两个相邻链节的粘合处对应欧拉游走停在同一顶点。

Hint 4

从 20 降序检查；第一个欧拉图直接用 Hierholzer 恢复每条边的方向。

Observations

只检查每个低位颜色出现偶数次还不够：两个互不相连的欧拉分量无法粘成一条项链。连通性与偶度缺一不可。
固定 $k$ 后，原链节 $i$ 是边 $(a_i\bmod2^k,b_i\bmod2^k)$。链节可翻转正好对应无向边可沿任一方向经过。
一条覆盖全部边的欧拉回路给出边序。相邻边共享的欧拉顶点意味着对应端点低 $k$ 位相同，因而粘合美丽值至少为 $k$。
若某项链达到阈值 $k$，沿链节内部看边、沿粘合处看公共顶点，它反过来就是该掩码图的欧拉回路。因此模型不是仅充分，而是充要。

Editorial、证明与复杂度

对 $k=20,19,\ldots,0$，建立 $2^k$ 个掩码点和 $n$ 条链节边。检查所有度数为偶数，再从任一非零度点运行 Hierholzer；若最终使用边数少于 $n$，说明非零度部分不连通。

可行时，把欧拉回路中的有向经过记为 from --edge i--> to。若 a_i 的掩码等于 from，输出端点 2i-1,2i；否则反向输出。这样每一对输出位置是同一链节，而前一链节的末端与后一链节的首端都代表同一欧拉顶点。回路首尾同理。

上述双向对应证明判定充要；降序枚举的首个可行 $k$ 即最优值。每轮 $O(n+2^k)$，几何级数 $\sum2^k=O(2^{20})$，总时间 $O(20n+2^{21})$，空间 $O(n+2^{20})$。

实现指南、核心伪代码与附件

for k from 20 down to 0:
    mask = 2^k - 1
    for each part i:
        add edge i between a[i]&mask and b[i]&mask
    if every degree is even:
        tour = Hierholzer from a nonzero-degree vertex
        if tour uses all n edges:
            orient every part by its traversal direction
            output k and the corresponding endpoint pairs
            stop

完整 GNU C++17 实现

扩展与联系

这一建模可推广到“固定二端物件必须全部串成一个环，接口只按等价类兼容”的问题：接口类作点、物件作边。若只需若干个环，连通性条件可删除，但答案会变成每个欧拉分量各造一环。

实现细节与失效边界

必须按边编号判重；自环会在同一点邻接表出现两次，但只能使用一次。
k=0 时只有一个掩码点，保证兜底可行。
Hierholzer 得到的边常为逆序退出序，输出前应整体反转，不能只翻转每条边。
若目标改成最大化粘合美丽值之和，阈值单调性消失，欧拉可行性不再直接给最优。

总结与自检

请独立证明“可行项链 $\Leftrightarrow$ 掩码图欧拉回路”，并手算一个偶度但不连通的反例。再回答：为什么从大到小枚举一定能找到最优阈值？

课后训练建议

先只输出最优 $k$，确认判定后再恢复端点方向；卡在构造 25 分钟后只看 Hint 3。完成后用随机小数据验证输出的端点恰好使用一次、链节成对且所有粘合低位相同。

02-高阶扩展-掩码图上的欧拉回路.md 5.3 KB History Raw