YZOJ P2417 [FJWC2016][CF79-D]翻转硬币

时间限制：1000MS      内存限制：131072KB

难度： \(6.0\)

• 题目描述

\(n\) 枚硬币正面朝上摆成一排，给定 \(a_1, a_2, \cdots, a_m\)，每次操作可以任意选择一个 \(a_i\)，并翻转连续 \(a_i\) 个硬币。

要求经过最少次数的操作，使得仅第 \(x_1, x_2, \cdots, x_k\) 枚硬币反面朝上，输出最少次数。

• 输入格式

第一行三个整数 \(n\)、\(k\)、\(m\) 。

第二行 \(k\) 个整数表示需要反面朝上的硬币位置，从 \(1\) 编号。

第三行 \(m\) 个整数表示 \(a_1, a_2, \cdots, a_m\) 。

• 输出格式

一个整数表示答案，若无解，则输出 \(-1\) 。

• 样例输入

• 样例输出

• 数据规模与约定

对于 \(30\%\) 的数据，\(n, m \leq 10\) 。 

对于 \(60\%\) 的数据，\(m \leq 20\) 。 

对于 \(100\%\) 的数据，\(1 \leq n \leq 10000\)，\(1 \leq k \leq 10\)，\(1 \leq m \leq 100\)，\(1 \leq a_i \leq n\) 。

 

 

 

Source: CF79-D

---

 

 

 

首先考虑连续翻转 \(a\) 个硬币的操作要怎么实现。

设 \(s_i \kern 4pt (1 \leq i \leq n)\) 为第 \(i\) 个硬币的状态，\(0\) 表示正面朝上，\(1\) 表示反面朝上。

当然最朴素的做法就是 for  一遍区间，把里面的每个数 \(s_i \kern 4pt \scriptsize\wedge=\normalsize \kern 1pt 1\) 。但是这样做显然是不优的。

发现因为每个硬币是正面朝上还是反面朝上只与翻转它次数的奇偶性有关，所以可以记一个差分数组（其实是异或数组）表示相邻两个 \(s\) 的异或值。即记 \(b_i = s_i \oplus s_{i+1} \kern 4pt (1 \leq i \leq n-1)\)，为了保证它的正确性，再令 \(b_0=s_1,\kern 4pt b_n=s_n\) 。第 \(i\) 个硬币的状态就可以通过 \(b_0 \oplus b_1 \oplus \cdots \oplus b_{i-1}\) 来表示。

这样就可以方便的表示出翻转一个区间内的所有硬币的操作。要翻转 \(l\) ~ \(r\) 内的所有硬币，只要把 \(b_{l-1}\) 和 \(b_r\) 都 \(\scriptsize\wedge=\normalsize \kern 1pt 1\) 就可以了。因为在前缀和（其实是前缀异或）的时候，更改了区间头前一位奇偶性，区间内的所有数的奇偶性也会对应改变；更改区间尾的奇偶性，区间外的数的奇偶性不受影响。

可以快速进行区间内的操作之后，再考虑这个问题的本质是什么。

初始状态的 \(s\) 为 \(\underbrace {0,0, \cdots ,0}_n\) ，差分后得到初始状态的 \(b\) 为 \(\underbrace {0,0, \cdots ,0}_{n + 1}\) 。

举个栗子，有一个 \(s\) 为 \(0,0,0,1,1\) ，差分后得到它的 \(b\) 为 \(0,0,0,1,0,1\) 。

因为操作的无序性，所以要求的答案就是把 \(b\) 中所有的 \(1\) 经过一系列操作后全部变成 \(0\) 的最小代价。这里的操作指的是把 \(b\) 中第 \(i\) 位和第 \(i \pm a\) 位同时翻转，进行这样一次操作的代价为 \(1\) 。

\(\begin{array}{l} 0,{\kern 4pt}0,{\kern 4pt}0,{\kern 4pt}1,{\kern 4pt}0,{\kern 4pt}1\\
 \downarrow {\kern 1pt} {\kern 10pt} \leftarrow 5 \to {\kern 9pt}  \downarrow \\ 1,{\kern 4pt}0,{\kern 4pt}0,{\kern 4pt}1,{\kern 4pt}0,{\kern 4pt}0\\  \downarrow {\kern 1pt} \leftarrow 3 \to \downarrow \\ 0,{\kern 4pt}0,{\kern 4pt}0,{\kern 4pt}0,{\kern 4pt}0,{\kern 4pt}0 \end{array}\)

如果第 \(i\) 位和第 \(i \pm a\) 位都为 \(1\) ，那么就可以通过一次操作把它们都变为 \(0\) 。

注意到可能会出现有第 \(i\) 位为 \(1\) ，而第 \(i \pm a\) 位不为 \(1\) 的情况。如果有解的话，那么第 \(i \pm a\) 位一定可以通过其他位的操作翻转为 \(1\) ，否则这两位将永远无法同时消掉也就无解了。

（这里本来好像有张图，但是我也忘了是什么图了。。。。

发现这样连锁操作的过程可以表示在一张无向图中，每次消掉一对 \(1\) 就表示图中的一条路径（注意：路径中可能会存在翻转 \(0\) 的中间节点）。所以把 \(i\) 和 \(i \pm a\) 连一条边权为 \(1\) 的无向边，对每一个 \(b_i=1\) 的 \(i\) 都跑一遍单源最短路即可算出把 \(i\) 和 \(j\) 同时翻转所需要的最小代价（记录 \(b_i=b_j=1\) 的最小代价即可，其他状态都是无用的）。这个过程可以使用 BFS  来实现。

最后的最后，知道了同时翻转 \(b\) 中两个 \(1\) 的最小代价，要求翻转 \(b\) 中所有 \(1\) 的最小代价。注意到因为 \(1 \leq k \leq 10\)，所以 \(b_i=1\) 的 \(i\) 的个数不会超过 \(20\) 个，可以想到 状压DP 。把 \(b_i=1\) 的数位的翻转状态压成一个二进制数，某一位上为 \(0\) 表示对应 \(b\) 中的这一位没有翻转，为 \(1\) 表示对应 \(b\) 中的这一位已经被翻转。答案的状态就为 \(2^{num}-1\) ，\(num\) 表示 \(b_i=1\) 的 \(i\) 的个数。

转移也很简单。对于当前状态 \(bin\) ，其中第 \(i\) 位为 \(1\) （快速取个 lowbit() 即可），枚举其他为 \(1\) 的位 \(j\) ，\(f_{bin}=min\{f_{bin-2^i-2^j}+dist_{i, j}\}\) （\(dist_{i, j}\) 表示同时翻转 \(i\) 和 \(j\) 对应 \(b\) 中的两个数位的最小代价）。

最后输出 \(f_{2^{num}-1}\) 即可，复杂度 \(O(knl + k \cdot 2^{2k})\) 。