题解：P9001 [CEOI2022] Parking

honglan0301 · 2024-04-19 15:08:09 · 题解

分析

<1> 首先不管空位数量的限制，先考虑如何让操作次数最少：

对每种颜色记录 二元组 (x_i,y_i)\in\{(0,0),(0,1),(1,1)\} 表示颜色为 i 的两辆车分别是/否位于靠近入口的一端，以及 (u_i,v_i) 表示它们初始停放的车位编号。那么对 (u_i,v_i) 连边建成图 G（形成若干个环与链），分讨可以得到操作次数的理论下界：

• *特别地，当一个连通块中全是 $(x_i,y_i)=(0,1)$ 的颜色时，至少要多进行一次操作。因为连通块中第一个被操作的颜色不能立即完成配对。

再尝试构造方案：

• 首先把 (x_i,y_i)=(1,1) 的颜色都换到初始局面的空位上。

• 此时图 G 里每条链中的 (x_i,y_i) 一定依次形如 (1,0),(1,0),\dots,(1,0),(0,0)，从前往后依次删即可；每个环中 (x_i,y_i) 一定只有 (1,0)，任选一个 1 换到空位处后，环变为链，用删链的方法即可。

• 因此能够找出操作次数达到理论下界的方案，sub2 得到了解决。

<2> 考虑在以上过程中，如何使得同一时刻占用车位数最少：

同样先分析下界，按照图 G 各连通块的形态/状态分讨：

• 对于一条链。操作时，如果其中仅有 (x_i,y_i)=(1,0)/(0,0) 的点，则对其操作时不需占用额外空位；否则至少要占用一个空位。操作后，空位数量增加 1（原先两端车位各只停一辆车）。

• 对于一个环。操作时，假如其中均有 (x_i,y_i)=(1,0) 或只有一个 (x_i,y_i)=(1,1)，则至少占用一个空位；否则至少占用两个空位（因为对其进行任何操作后均会变成含有 (1,1) 的链）。操作后，空位数量保持不变。

再构造/判无解：

• 首先操作不需额外空位的链。

• 此时若没有空位但仍需操作 则无解。

• 然后操作需要占 1 个空位的链（因为能够提供新空位）。

  *具体地，我们从链头开始，每当碰到 (x_i,y_i)=(1,1) 的颜色就将其换到空位处，并将其前面不含 (1,1) 的链复原即可，占用空位数达到理论下界。

• 此时若空位数量为 1 但存在需占用两个空位的环 则无解。

• 否则对环依次操作，即可在操作次数最少的前提下完成任务。

  *具体地，先把环上一个 (x_i,y_i)=(1,1) 的颜色（如果没有就选 (0,1) 的颜色） 换到空位处，之后即可按照链的方法操作，占用空位数能够达到理论下界。

综上，做完了。简单维护即可做到线性。

代码

丑陋的 赛时代码。