题解：P8477 「GLR-R3」春分

STA_Morlin · 2024-11-25 11:04:28 · 题解

其实不是题解。

题目。

这题好题啊，有趣。

考虑几个关系：

1. 我们只需要 2\times n 个干净的面；
2. 每两个面是绑定在一起的；
3. 每单独的一块板只能用在一次实验中。

我们到底需要多少？

根据关系一，我们似乎只需要 n 块板子，但是又根据关系三我们可以看出事情并不是那么简单。

考虑你要进行 n^2 次实验，所以至多只需要 n^2 块板。

不对板子进行拼接是很浪费的，故我们必然拼接，所以提出几个拼接关系：

1. 拼接的两个面必然应是用完的面，上面的液体也应该是全部试验完成的液体；
2. 一个面上有 2 种液体与有 n(n > 2) 种液体本质相同，与有全部试验完成的液体也相同；
3. 将同种液体拼接优于不同液体拼接。

这就意味着其实我们需要的是与 X 的 n 种液体相交的 n 个面，与 Y 的 n 个面，和一部分用了充当中间的面，这些面显然应该来自前面的 2n 个面当中。

哎呀哎呀，编不下去了，回去写 dp 了。