ABC略。
D. Make It Round
问题可以看成凑出尽可能多的 \(10\) 作为因子。
注意到 \(10\) 的因子只有 \(1, 2, 5, 10\)。
首先，\(n\) 自己已经凑出来的 \(10\) 没必要拆开，并不会更优。
然后就是看 \(n\) 有多少个多余的 \(2\) 或者 \(5\)，然后 \(k\) 先尽可能把这些多余的 \(2\) 或者 \(5\) 凑满，然后 \(k\) 再尽可能的自己凑 \(10\)，然后就无法继续增加尾部的 \(0\) 了。
注意到要求输出最大值，这个就是再加一步简单数学。
E. The Humanoid
观察：一定是吃到没有办法再吃了之后再嗑药。因为对于 \(k \in \{2, 3\}, y \ge 0\) 有 \(k(x + y) \ge kx + y\)。
这个过程可以借助小顶堆模拟，但是有一共3颗药，嗑药的顺序也会影响结果，但是也只有3颗药，枚举一下全排列即可。
F. All Possible Digits
观察1：至多操作 \(p – 1\) 次。因为前 \(p – 1\) 次操作，\(a_n\) 这个位置（叫做个位吧）每次操作都会生成一个个位上没有出现过的数。
推论1：个位至多产生一次进位。
推论2：出现的数，要么是初始就有的，要么是在个位产生，要么是进位产生的。
借助以下过程判断是否需要进位：
- 用一个
std::set存出现过的数。 - 令 \(x = a_n\)
- 若 \(x\) 出现过，则令 \(x = x – 1\)，重复步骤3；否则进行步骤4。这里的 \(-\) 是模 \(p\) 减。
- 根据 \(x\) 相对 \(a_n\) 的大小就可以判断是否需要进位。
易得这个过程的时间复杂度为 \(O(n \log n)\)。
不需要进位已经可以直接计算出答案了。
进位的话会产生一个或者多个 \(0\) 和一个非零值，模拟一次大数加法可以得到这个非零值。恰好进位完之后，如果没有没有出现过的数，那么答案为 \(p – a_n\)，否则没有出现过的数一定小于 \(a_n\)，假设没有出现过的数的最大值为 \(y\)，也就是个位数再增加到 \(y\) 就完成目标了，答案为 \(p – a_n + y\)，这个通过一个类似判断进位的过程就可以得到。
G. Restore the Permutation
因为 \(b_i\) 是较大值，所以它一定靠后，即 \(p_{2i} = b_i\)，此外较小值对应的位置必为 \(2i – 1\)，不妨记 \(b_i\) 对应的坑位为 \(2i – 1\)。
然后就是贪心：从大到小枚举没有出现过的数，然后把它尽可能往后排。正确性显然。
实现的话，假设初始时所有位置都不可用，然后从大到小枚举所有数，假设枚举到 \(x\)，如果 \(x\) 已经出现过了，那么把 \(x\) 对应的坑位设为可用；如果 \(x\) 没有出现过，如果没有可用的位置则无解，反之就把 \(x\) 放到最靠后的可用位置上。
借助 std::set 或者大顶堆维护一下可用位置就能做了。
原文地址：http://www.cnblogs.com/zengzk/p/16905355.html
