队伍训练，个人做了 G, F, H, C, D，都是不难写的，还是菜……
G - Lucky 7 in the Pocket#
签到。
F - Abbreviation#
签到。
H - Singing Everywhere#
删除一个点只会影响到两边是否是 “voice crack”，因此存一下前缀和后缀的 “voice crack” 的数量，再加上两边的情况即可。
C - Array in the Pocket#
如果最多的元素，数量是超过一半的，那就没有办法满足重新排列后满足题目的条件。
进一步地，如果需要放置的元素不为原序列 $A$，而是另外的一个大小和原序列长度相同的多重集 $S$，那么只有当所有元素在 $A$ 和 $S$ 出现的总数不超过 $|A|$，才会有解。同时，如果有元素出现的总数为 $|A|$，那么该元素重排的位置是确定的。
对于这个题目，大思路确实是尽可能地放小的，但是存在情况需要放更劣的值。
假设前面已经放好了 $i - 1$ 个元素，还剩下没有放置的元素的多重集为 $S$：
- 若 $a[i:n]$ 和 $S$ 的所有元素中，总数最多的元素 $v$，数量若为 $n - i + 1$（即说明 $v$ 能放的位置，对于当前情况已经是固定的了），当 $a_i \ne v$ 时，则不得不放置 $v$ 在当前位置。
- 若 $a_i \ne \min{S}$，则可以放 $\min{S}$。
- 若 $a_i = \min{S}$，那就放次小的。
代码：写残了，可以写的更优雅一点。
D - Traveler#
后期就剩下 D 和 A 在写，D 我有个和队友不一样的方法，就偷偷写了一下。
我们首先从根节点走到节点 $n$，走过这条树链后，剩下未走过的点形成若干个完全、满二叉子树。接下来通过 $i - 1$ 的边走到相邻的一个子树，然后进行从一个子树的最右端走到最左端的操作。重复这样的操作直到 $i - 1$ 走到 $n$ 所在的树链为止。
你会想说走到整棵树的最左端的叶子节点后该怎么办。会发现通过 $i - 1$ 的边可以走到整棵树浅一层的最右端的节点，也就是剩下还没有走过的点形成在最右侧子树的最右端。
实现从子树的最右走到最左操作，同时，还需要实现一下从最右走到根、从根走到最左。然后这三个操作之间递归一下即可完成子树的遍历。
代码：写残了，可以写的更优雅一点。
评论