题解 P4794 【[BalticOI 2018]交流电】

### Alternating Current ### 交流电 **翻译自 [BalticOI 2018 Day 2 题解](https://boi2018.progolymp.se/spoiler-day2.pdf)** **注意：由于洛谷搬运题面时出了一些锅，导致题面与题解不一致，建议参考 LOJ 上的题面阅读。** #### 子任务 1 注意到一共只有 $2^M$ 种可能情况，所以当 $M\leqslant15$ 时我们可以简单的枚举所有情况判断是否满足条件。为了检查一种方案，我们可以枚举子集，分别判断某一段线段的颜色。这样的算法时间复杂度为 $\mathcal{O}(2^MMN)$。 #### 子任务 4 区间不会跨越第 $N$ 条线段，所以控制点存在一个自然的顺序，我们对所有区间按左端点排序，然后贪心地逐一给它们分配的颜色。 当我们遇到一个区间时，我们的选择是将它染成红色或蓝色。如果红色的区间右端点大于蓝色的区间右端点，因为红色和蓝色区间同样都要覆盖圆的一周，显然我们应该将这个区间染成蓝色，使得红色与蓝色区间尽量保持同步前进（注意这个对称应该从起点开始）。否则我们就将这个区间染成红色。如果区间出现了中断，答案就是 ``impossible``，否则这个贪心算法就是有效的。 #### 子任务 5 通过观察我们可以发现，如果一个区间 $w$ 只能对另外一个区间 $w'$ 覆盖的一个子集进行染色，我们可以不失一般性地将区间 $w$ 染成与区间 $w'$ 相反的颜色。因为将区间 $w$ 染成与区间 $w'$ 相同的颜色不会产生任何效果。因此我们用下面的方式为更多的区间分配_祖先_： - 如果区间 $w'$ 是区间 $w$ 的祖先，则区间 $w$ 覆盖了区间 $w'$ 覆盖范围的一个子集； - 如果一个区间的祖先是它自己，则说明这个区间没有祖先。 通过以上方式，我们已经将所有的区间分成了两个不相交的集合：作为某些区间的祖先的区间和作为某些区间后代的区间。从现在开始我们将把注意力集中在作为某些区间的祖先的区间的集合，并将其记作 $\mathcal{W}$。 在集合 $\mathcal{W}$ 中的区间 $w$ 不会覆盖同属集合 $\mathcal{W}$ 中的另一个区间 $w'$ 的一个子集，因为如果出现了这种情况，$w'$ 就应该是 $w$ 的祖先了。相反，集合 $\mathcal{W}$ 中的区间只有一部分重叠或完全不相交。 我们现在按区间左端点将集合 $\mathcal{W}$ 中的区间排序，并令 $w_1,\,\ldots,w_k$ 表示集合 $\mathcal{W}$ 中已经排好序的一部分。可以证明以下引理成立： > **引理 1** 假设 $k$ 是偶数且存在一组解。将区间 $w_1,\,w_3,\,w_5,\,\ldots,\,w_{k-1}$ 染成一种颜色，将区间 $w_2,\,w_4,\,w_6,\,\ldots,\,w_k$ 染成另一种颜色一定是一组合法解。 > **证明** 我们使用反证法证明这个引理。假设存在一些线段 $s$ 不能按引理中所述的方法被染成两种颜色。因为存在一组合法解，所以所有的线段都会被至少一个集合 $\mathcal{W}$ 中的区间染色。所以我们假设区间 $w_i$ 对线段 $s$ 进行了染色。如果区间 $w_{i-1}$ 或 $w_{i+1}$ 对线段 $s$ 进行了染色，则线段 $s$ 会被染成两种颜色。因此 $w_i$ 是集合 $\mathcal{W}$ 中唯一对线段 $s$ 进行染色的区间。这意味着所有其它（不在集合 $\mathcal{W}$ 中的）对线段 $s$ 进行染色的区间一定是区间 $w_i$ 的后代，但是这样我们就能使得它们的颜色与区间 $w_i$ 不同，所以 $s$ 可以被这些区间染成两种颜色。证毕。 引理 1 说明了当 $k$ 为偶数时，我们可以给区间 $w_1,\,\ldots,\,w_k$ 交替赋值为 $0$ 和 $1$，然后检查是否为合法解。 当 $k$ 为奇数时的情况稍微难一些，对于这种情况我们提出以下引理： > **引理 2** 假设 $k$ 是奇数且存在一组解。存在一个 $i$ 使得将区间 $w_i,\,w_{i+2},\,w_{i+4},\,\ldots,\,w_{i-1}$ 染成一种颜色，将区间 $w_{i+1},\,w_{i+3},\,\ldots,\,w_{i+2}$ （式中所有下标对 $k$ 取模）染成另一种颜色为一组合法解。 > **证明** 考虑一组合法的染色方案。因为 $k$ 是奇数，存在一个 $i$ 使得这个合法的染色方案将区间 $w_{i-1}$ 与区间 $w_i$ 染成同一颜色。我们断定如果我们按引理所述进行染色，一定存在一组合法解。我们同样使用反证法证明这个引理。假设有一些线段 $s$ 不能按引理中所述方法被染成两种颜色。因为存在一组合法解，所以线段 $s$ 一定会被至少一个集合 $\mathcal{W}$ 中的区间 $w_j$ 染色。 > 假设线段 $s$ 被某个满足 $w_j\in\mathcal{W},\ j\not\in \{i-1,\,i\}$ 的区间染色。如果区间 $w_{j-1}$ 或区间 $w_{j+1}$ 也能对线段 $s$ 进行染色。因此，线段 $s$ 会被染色两次。所以我们假设区间 $w_j$ 是集合 $\mathcal{W}$ 中唯一对线段 $s$ 进行染色的区间，则所有其它覆盖线段 $s$ 的区间一定是区间 $w_j$ 的后代，这意味着这些区间会被染成与区间 $w_j$ 不同的颜色，所以线段 $s$ 会被这些区间染成两种颜色。证毕。 对于子任务 3，枚举每一个可能的 $i$ 并检查染色结果就够了。对于子任务 5 我们则需要优化。一个将区间 $w_i,\,w_{i+2},\,\ldots,\,w_{i-1}$ 染成一个颜色，并将区间 $w_{i+1},\,w_{i+3},\,\ldots,\,w_{i-2}$ 染成另一种颜色的染色方案合法，当且仅当： 1. 所有线段至少被一个区间染色； 2. 对于所有的 $j\not\in\{i-1,\,i\}$，区间 $w_{j-1},\,w_j,\,w_{j+1}$ 与它们所有的后代一同将被区间 $w_j$ 染色的线段染成两种颜色； 3. 区间 $w_{i-1},\,w_{i},\,w_{i+1},\,w_{i+2}$ 和它们所有的后代一同将所有被区间 $w_i$ 和 $w_{j+1}$ 染色的线段染成两种颜色。 上述要求 1 和 2 几乎与对 $i$ 的取值无关（除非我们需要保证 $j\not\in\{i-1,\,i\}$），所以当我们改变 $i$ 的取值时，我们只需要检查要求 3 是否满足，这可以在均摊常数的时间复杂度内完成。 以上算法的时间复杂度主要取决于找到区间的祖先和对集合 $\mathcal{W}$ 进行排序。渐进时间复杂度为 $\mathcal{O}(M\log M)$。