传送门
一道有趣的思维题。
我们从最简单的情况开始考虑:如果还剩下 \(2\) 格电呢?
那么直接询问 \(\texttt{O}\) 和 \(\texttt{H}\),剩下的位置就是 \(\texttt{C}\)。
从以上的朴素做法中我们得到启发:能不能通过耗电量更低的方式来确定三个字母的所有位置?
询问一个长度为 \(t\) 的串的耗电量是 \(\frac{1}{t^2}\),注意到分母越小(即询问的字符串长度越短)耗电量越大,因此我们希望尽可能加长询问的串的长度。
考虑询问 \(\texttt{CC,CH,CO}\),这样我们可以确定(除了最后一个字母以外)所有 \(\texttt{C}\) 的位置。再询问 \(\texttt{OO,HO}\),这样我们可以确定(除了第一个字母以外)所有 \(\texttt{O}\) 的位置。这时我们消耗了 \(1.25\) 格电量。
现在我们至多只剩下第一个字母和最后一个字母不确定,因此我们至多再进行三次询问就能够确定完整的串是什么。具体地,第一个字母只有可能是 \(\texttt{H,O}\) 两种情况(如果是 \(\texttt{C}\) 已经在以上的第 \(1\) 到 \(3\) 个询问中被问出来了),最后一个字母只有可能是 \(\texttt{C,H}\) 两种情况(如果是 \(\texttt{O}\) 已经在以上的第 \(3\) 到 \(5\) 个询问中被问出来了)。
经过计算,当字符串长度大于 \(4\) 的时候,总耗电量是小于 \(1.4\) 的(长度为 \(4\) 时总耗电量为 \(1.4375\),长度为 \(5\) 时总耗电量为 \(1.37\))。
因此我们以下考虑字符串长度等于 \(4\) 的情况。
首先还是要询问 \(\texttt{CC,CH,CO}\),如果三个中有至少一个出现了,那么就已经有至少两个位置确定了。并且如果字符串中还有 \(\texttt{C}\) 没有被问出,则这个 \(\texttt{C}\) 只有可能在最后一位。
此时如果最后一位已经被确定,则一共有 \(4\) 种可能的情况(以最后两位已经被确定为例,分别为 \(\texttt{HH**,HO**,OH**,OO**}\),\(\texttt{*}\) 处为已经被确定的字母)。如果最后一位没有被确定,则一共有 \(6\) 种可能的情况(以前两位已经被确定为例,分别为 \(\texttt{**HC,**OC,**HH,**OH,**HO,**OO}\))。则至多只需进行 \(5\) 次询问,最多耗电量为 \(1.0625\)。
如果以上三者都未出现,再询问 \(\texttt{HO}\),如果出现过,则至多有 \(6\) 种可能的情况,与以上同理,最多耗电量为 \(1.3125\)。
如果以上四者都未出现,再询问 \(\texttt{OO}\),如果出现过,此时原字符串有可能是 \(\texttt{OOOO}\) 或 \(\texttt{OOO?}\) 或 \(\texttt{OOH?}\)(\(\texttt{?}\) 处为未确定的字母)。如果是第一种情况,则此时已经确定,询问结束,总耗电量为 \(1.25\);如果是第二种情况,则前三位已经确定,再询问一次即可(因为最后一位不能是 \(\texttt{C}\)),总耗电量为 \(1.3125\);如果不是前两种情况,则第三位也已经确定是 \(\texttt{H}\),与第二种情况同理,再询问一次即可。
如果以上五者都未出现,则该字符串一定是 \(\texttt{?HH?}\) 的形式(因为如果中间两位出现 \(\texttt{C,O}\),应当在前五次询问中被问出),此时第一位可能是 \(\texttt{C}\) 或 \(\texttt{H}\),最后一位可能是 \(\texttt{O}\) 或 \(\texttt{H}\)。此时询问 \(\texttt{HHH}\),则所有 \(\texttt{H}\) 的位置都已被问出,那么根据排除法就能确定第一位和最后一位的位置。总耗电量约为 \(1.3611\)。
将以上两种情况合起来,本题就完成了。
本题分讨比较复杂,蒟蒻只会暴力地写一大堆条件判断,导致代码很不优美,就不放了,大家可以看其他大佬更加简洁的实现方式。