Luogu P3943 - 星空

Author Avatar
Jimmy Zhang Feb 05, 2019
  • Read this article on other devices

题面

现有一个长度为 nn 的灯泡序列,其中 kk 个位置上的灯泡是熄灭的,其余的是点亮的。我们可以进行 mm 种操作,而第 ii 种操作是选定任意长度为 bib_i 的连续灯泡区间,对这个区间内所有灯泡的状态都进行一次翻转(亮变灭,灭变亮)。试求最少需要几次操作就可以让所有灯泡都被点亮。

数据范围

1n,bi4×1041 \le n, b_i \le 4 \times 10^4

1m641 \le m \le 64

1k81 \le k \le 8

题面链接

分析

差分思想

我们首先考虑如何快速对区间进行操作,而将区间操作转换为单点操作最常见的方法就是差分数组。不过这里我们面对的是一个 01 序列,我们可以把前缀和改成异或和,这样一来我们只需要翻转端点就可以达到区间修改的目的了。严格地说,记 aa 代表原 01 序列,dd 是原序列的异或差分数组。那么它们之间存在如下关系:

ai=b0b1bia_i = b_0 \oplus b_1 \oplus \dots \oplus b_i

如果我们需要翻转 aa 中的 [l, r] 区间,只需要在 bb 中翻转 llr+1r + 1 两个位置即可。由此一来,我们实际上把 aa 中的区间操作转换为了 dd 中的单点操作(注意 dd 的长度是 n+1n + 1)。那么我们可以把原问题转换为这样一个新问题:给定一个 01 序列 dd,一次只能选择两个位置上的值(这两个位置间隔的距离是题面给出的 mm 种)并对其进行翻转,试问最少翻转多少次可以将序列翻转成目标序列。

我们不妨记灯亮为 00,灯暗为 11。这里这样记仅仅是为了方便,因为由此一来所有灯全亮时 aa 为全 00,而其对应的 ddnn 个位置也为全 00。至于 dd 中的第 n+1n + 1 个位置,不论其为 00 还是 11 都不会对 aa 产生任何影响,因此第 n+1n + 1 位可以是任意值。

需要注意的是,题目给出了 aa11 的个数 k8k \le 8,这一限制对应到差分数组 dd 中会是怎样呢?如果我们要让 dd111111111111\dots,那么 aa 的形式即如 101010101010\dots。不难发现若 aa 中最多有 kk11,则 dd 中最多有 2k2k11

完全背包

接下来我们来考虑转换后的问题。我们每次可以选择两个点进行翻转,为了让反转次数最少我们肯定不会选择两个 00 进行翻转,因为这样只会使得 11 的个数增多;如果我们选中两个 11,那么翻转后两个位置上的值都会变为 00。而如果我们选择一个 00 和一个 11 翻转,那么这次操作后 11 的个数并不会变化,其效果等效于将选中的两个位置上的值交换位置。进一步说,如果记两个位置间的距离为 Δx\Delta{x},则我们可以认为是 11 向左或是向右移动了 Δx\Delta{x}

那么问题可以进一步转换为:给定一个 01 序列,对于序列中每个 11,每一步可以向前或向后走 kk 种距离,如果走到的位置上也是 11 则两者相消为 00,问最少需要多少步可以使得所有位置都变为 00

若某一对 11 之间的距离为 Δx\Delta{x},则若要将这对 11 相消,就需要左右两端的 11 分别向左和向右移动到同一位置上。我们不妨把 Δx\Delta{x} 看作背包容量,每种可能的步数看作背包里的物品(每种步数 vv 要拆成 +v+vv-v 两个物品,因为既可以往左走又可以往右走),那么我们 O(nm)\mathcal{O}(nm) 跑一个完全背包就可以得到消去每一对 11 所需要的最小步数。

一般图的最大匹配

在得到了消去每一对 11 所需要的最小步数后 ww,我们可以考虑在这两个点间建立一条价值为 ww 的无向边。这样一来,问题就转变为了一般图的最大匹配问题…… 大佬们可以使用带花树算法用 O(k3)\mathcal{O}(k^3) 级别复杂度解决之…… 当然这道题数据范围很小,所以我们也可以使用状压DP来解决。

最后还有一个细节,前面说了 dd 中第 n+1n + 1 位可以是任意值,因此如果考虑这一位会带来一些不便。我们可以这样处理:如果位置 ii 经过若干步可以到达第 n+1n + 1 位,我们就从 ii 向自己连一条边。其意义为 ii 可以与自己进行匹配。这样子就可以完全去掉第 n+1n + 1 位从而简化模型。

为了减小状态数量,我们不妨只考虑所有 11 点。这样一来,初始状态用二进制表示就是 11111\dots1,而目标状态即为 00000\dots0。在 DP 过程中,我们不必要用 O(k2)\mathcal{O}(k^2) 的复杂度去枚举每一个点对,因为那样会造成大量重复运算。事实上,我们可以每次选取最左的 11 点作为点对的一个点,然后 O(k)\mathcal{O}(k) 枚举另一个点直接进行转移即可。这样子其实是可以遍历到所有状态的(反正目标状态中这个 11 迟早要消去)。因此状压 DP 的复杂度为 O(k2k)\mathcal{O}(k \cdot 2^k)

实现

总的复杂度为 O(nm+k2k)\mathcal{O}(nm + k \cdot 2^k)

这里是用完全背包+状压DP实现的,或许等我学会带花树算法后还会来诈尸

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2019/02/05/luogu-p3943/