题解：CF1292E Rin and The Unknown Flower

TTpandaS · 2025-10-16 09:05:49 · 题解

以下将 C，H，O 分别写作 1，2，3。

首先考虑查询长度为 1 的串，即通过直接询问 ? 1 3 和 ? 1 2，花费 2 的代价找到所有 2,3 的位置，那么剩下的就是 1 的位置。

再考虑查询长度为 2 的串，即通过询问 ? 2 a b（a=1,2,3,b=1,2,3）来确定所有位置。? 2 1 1 在得知其他信息后没有必要询问。而 ? 2 1 2 和 ? 2 2 1 在得知其他信息后可以改成询问 ? 3 1 2 1，同理，? 2 1 3 和 ? 2 3 1 在得知其他信息后可以改成询问 ? 3 1 3 1。此时前两个和后两个可能不确定。如果第二个位置确定而第一个位置不确定，第一个位置只能为 1。如果两个都不确定，那么可能为 1 1，2 1 或 3 1，加上以确定的中间部分，查询 3 1 ... 和 2 1 ... 即可。后两个位置同理。1.22+\dfrac{2}{n^2}+\min (\dfrac{2}{（n-2)^2},\dfrac{6}{n^2})，在 n>4 时可以通过。