题解：P1431 找出伪币

· · 题解

P1431 题解

这题算是比较水的紫题。

显然，此题需要分类讨论。

此时我们猜测答案为 $⌈ \log_2 n ⌉$。但我们发现，天平不一定一次只能称量两份。我们可以剩余一份出来。假设现在要判定的硬币数为 $3$ 的倍数，假币比真币重。 令天盘左盘所有的硬币为 $\{l_n\}$，右盘为 $\{r_n\}$，剩下的为 $\{m_n\}$ 。具体的方法如下： 如果比较之后得到左盘比右盘重，则右盘中有假币；若右盘比左盘重，则左盘中有假币；若两盘一样重，则剩余硬币中有假币。 所以对于 $p \neq 0$ 时，答案为 $⌈ \log_3 n ⌉$。 --- 当 $p = 0$ 时，考虑正难则反。 首先我们知道，称 $2$ 次可以解决 $3$ 枚硬币的问题。只需要将左边换一枚即可得到假币和假币与真币的关系。 同理，我们可以手算出 $3$ 次可以解决 $12$ 枚，$4$ 次可以解决 $39$ 枚。所以称 $x$ 次可以得到 $\sum_{i=1}^{x-1} 3^i = 3^x - 3$ 枚（~~这个式子不会推导建议重学初中知识~~）。从而得到，称 $k$ 枚需要 $⌈ \log_3 (2n+3) ⌉$ 次。 代码就不放了，太卡常不好。