标签：查集 MEX cdots 答案 集合 Walk 拆位

算法

性质

首先容易观察到

\[\text{mex} (w_1, w_1 \And w_2, w_1 \And w_2 \And w_3,\cdots , w_1 \And w_2 \And w_3 \And \cdots w_k) \]

中 集合

\[{w_1, w_1 \And w_2, w_1 \And w_2 \And w_3,\cdots , w_1 \And w_2 \And w_3 \And \cdots w_k} \]

显然是单调不增的

显然答案取决于集合的后几位
考虑拆位

拆位

• 答案为 \(0\)

当集合中不存在 \(0\) 时, 答案显然为 \(0\)
即存在一条路使得路径上的边权集合, 有一位都为 \(1\)
考虑用并查集实现

对每一位, 如果当位为 \(1\) , 那么加入并查集
判断答案是否为 \(0\) , 即为判断两点是否连通

• 答案为 \(1\)

对于集合中的某一位 (不为末尾因为不能存在 \(1\))
存在一种使下面两个成立

1. 前连续几个都为 \(1\), 这样就能满足集合中拥有大于 \(1\) 的数
2. 后连续几个都为 \(0\), 这样就能满足

标签：查集,MEX,cdots,答案,集合,Walk,拆位
From： https://www.cnblogs.com/YzaCsp/p/18449191