思维题选记

洛谷 P1146 硬币翻转

首先，有一个关于硬币翻转的性质，就是一个硬币只有翻转奇数次才能反面朝上，这是显然的。这启发我们构造一种能使每个硬币翻转奇数次的方案。

同时，我们发现对完全相同的一组 $n-1$ 个硬币执行两次及以上的操作是没有意义的，因为执行奇数次的话，就相当于 $1$ 次。偶数次的话就相当于什么都没有做。所以说方案数最大就是 $n$ 次，因为不同的操作序列只有 $n$ 个。

有了以上两个性质，我们便可以构造如下方案：

第 $i$ 次翻转除第 $i$ 枚硬币以外的 $n-1$ 枚硬币，其中 $1 \leq i \leq n$。

这样的方案中显然每一枚硬币都被翻转了 $n-1$ 次，由于 $n$ 为偶数，所以符合性质一。这样操作次数共有 $n$ 次，可以证明这是最小的方案数，同时也符合了性质二。这样的方案也是字典序最小的方案，所以这就是正确的解法。

洛谷 P1031 [NOIP2002 提高组] 均分纸牌

首先定义 $\texttt{avg}$ 为纸牌总数的平均数。如果要使每堆纸牌的数量一样多的话，那么经过移动后要使 $A_i=\texttt{avg}$。

对于第一堆牌，它只能向第二堆牌索取，或者进行给予。设 $x=A_i-\texttt{avg}$。如果 $x>0$，那么就把多的给第二堆。如果 $x<0$，不管怎么移动，必然有一步是第二堆给第一堆 $\lvert x \rvert$ 张牌。上述两种情况答案需要加 $1$。如果 $x=0$，就不用管了。

此时我们发现第一堆牌已经符合条件了，那么第一堆就可以直接忽略了，此时第二堆就变成了第一堆，继续重复上述步骤。

如何说明这样做是最优的呢？我们发现在上述过程中，每一步都是必须的，没有多余的步骤，所以其必然是最优解，这也是贪心思想的体现。

如果移牌的过程中出现负数怎么办？对于这个问题，可以发现移牌的步骤的顺序不是固定的，这样，我们就可以每次移动不会出现负数的牌堆，这样的方案是一定存在的。

洛谷 P1017 [NOIP2000 提高组] 进制转换

十进制数转负进制，同样可以使用短除取余法，但是会出现余数为负的情况，例如 $-11 \div -2 = 5 ~\cdots \cdots -1$，此时我们可以用如下法方解决此问题：

我们设被除数为 $a$，除数为 $b$，余数为 $c$，商为 $d$，其中 $c<0$ 且 $b<0$。

由除法的定义可知 $a=b \times d +c$，所以有 $a=b \times (d+1)+c-b$，由于余数小于被除数，所以有 $c \lt b$，又因为 $c<0$ 且 $b<0$，所以新的余数 $c-b > 0$。

所以我们只需要将商加 $1$，余数减除数，即可解决余数为负的情况。