Riddle

P6378 [PA2010] Riddle-2sat优化建图 \(n\) 个点 \(m\) 条边的无向图被分成 \(k\) 个部分。每个部分包含一些点。 请选择一些关键点，使得每个部分恰有一个关键点，且每条边至少有一个端点是关键点。 \(1\leq n,m\leq 10^6\) 边的限制 用 \(n ......

知识点：2-SAT，优化建图 Link：https://www.luogu.com.cn/problem/P6378。 2-SAT 前后缀优化建图套路。 对 2-SAT 本质的理解。 简述 给定一 \(n\) 个节点 \(m\) 条边的无向图，该无向图的所有节点被分为了 \(k\) 个部分。 要求选 ......

### 基本思路 明示了在二进制下考虑问题，我们大体的思路就是从高往低依次确定最大的数二进制下每一位上的值。 以下所述的「前缀」均指一个二进制数从高位到低位的一部分，一个元素的「前 $k$ 位」表示二进制从高位到低位的前 $k$ 位，$res$ 表示当前记录的最大前缀的长度。 先看看操作能干嘛，一是 ......