P7119 Mivik 的游戏 题解

先从一个例子开始

假如硬币开始是这样的:

HHHHHTHH

然后就可以将这个反面硬币 \(T\) 左边的硬币全都反过来，共需 \(5\) 步。

然后就变成了：

TTTTTTHH

最后再将最右边两个反过来就可以了，共需 \(5 + 2 = 7\) 步。

如果 \(p\) 为这个反面的硬币位置的话，那么答案 \(as = 2p - 1\)。

推导通项

我们考虑一下这个情景：

共有 \(m\) 个硬币反面朝上，\(k\) 此时等于 \(m\)。

\(k\) 不断加一，直到碰到另一个反面硬币，再回去。

设此硬币位置是 \(p_1\),则所用的步数 \(as_1 = (p_1 \times 2)- m \times 2 - 1\)。

然后不断推导 \(p_2,p_3,...\) 的公式，以此类推，就得到了通项：

关于本题的无解情况

最会骗分的方法肯定是先在程序中打上这么一行：

printf("never\n")

然后你就会发现：\(0pts\)。

所以说：这道题根本没有无解的情况。

那么这个结论是怎么得到的呢？

无解的情况只有一种，那就是在一个反面硬币的左边，还有 \(k\) 个反面硬币。

但是左边一共就能放 \(k - 1\) 个硬币，所以说本题不可能无解。