这些题解是边做题边打的，因此较为省略，

旨在尝试让自己讲明白题目是否能起到贯通思路、减少错误的作用。

A. Everybody Likes Good Arrays!

大意

求最少操作次数使得相邻元素奇偶性不同，

操作为将两个相邻且奇偶性相同的元素合并为乘积。

思路

相同奇偶性乘法不改变奇偶性，所以贪心即可。

维护数据

  • f / 答案
  • x, x0 / 新旧读入数字

坑

  • i = 0 的时候与上一个数字奇偶性相同也不应该加答案！

B. Emordnilap

大意

对每个排列，取其反转后结果拼在后面，求所有情况逆序对数量之和。

思路

数组前后两半逆序对数量之和为 n(n−1)2\frac{n(n - 1)}{2}，

跨越中线的逆序对数量也一样，所以总共是 n(n−1)n(n - 1)。

总共有 n!n! 种排列，因此结果为 n!n(n−1)n!n(n - 1)。

维护数据

  • f / 答案

C. Quiz Master（没做出来）

大意

从给定学生中选一些人，最小化学生智力极差，使得对 [1,m][1, m] 存在学生智力是其整数倍。

思路

智力可以用桶存储，每个小于等于 mm 的数都可以筛掉一部分人

但是对于一个任务，只需要有人会做即可。

优先考虑最大的数似乎并没有什么实际意义。

考虑贪心，但不能保证有确定要上场的人，方案的数量是指数级别的。

考虑从任务编号连续的角度入手，但学生智力是给定的，没有较好的处理方式。

实际上所有任务中有效的只有其中所有的素数，数量是对数级别的。

如果对于每一个数字，都能选择很多个学生，就会比较难办。

同时，低位的不一定是更优的解法，比如 T=3T = 3 时选择智力为 6 的学生最优。

对于每个任务，都存在一个集合，从每个集合中选择一个数，如何最小化极差？

枚举最后一个集合的元素，前面采用贪心策略，实现可能比较困难。

感觉情况相当复杂，比如学生是 4,5,6,7,6!{4, 5, 6, 7, 6!}，

T=6T = 6 时 6!6! 最优，T=7T = 7 时 4,5,6,7{4, 5, 6, 7} 最优。

可能的突破点在于 a 的范围被限制了。

可以确认至少有一个大于等于 TT 的学生要被选择。

每个集合里面的数可能分布是散的，因此可能没有比较 problem-specific 的策略。

考虑两个集合的情况，对于第二个集合中每个点，需要分别找上下匹配的第一个集合中的点，

同时大概还需要记录区间。

对第三个集合，则会出现难以比较的问题，而且感觉复杂度也会爆炸。

这说明可能存在小技巧，或者看错题了。

如果将问题看成查找一个区间的学生呢？

直接进行区间收缩可能漏掉最优解。

对区间头和区间尾分别二分？区间头不可二分。

由于如果区间 A 完全包含区间 B，区间 A 不可能是最优解，

因此可以直接使用双指针维护区间信息。

D. Score of a Tree

大意

对于一个 nn 节点、每个点为 00 或 11 的树，

进行一次操作后每个节点的值变成直接子节点异或结果，

求每种可能情况下每次操作后权值和。

思路

对于每种情况显然结果不同，考虑能否编组。

考虑将相反的情况编组，

  0
0   0
  0 0 1
---
  0
0   1
  0 0 0
---
  1
0   0
  0 0 0

  1
1   1
  1 1 0
---
  0
0   0
  0 0 0

可见没有明显规律，和奇偶性相关。

不同层级的子节点贡献不同，偶数相邻子代会抵消。

考虑递归计算总和，记录某一节点为 1 的情况数、局部情况总数、子代数量、局部总和，

讨论直接子代数量：

  • 为 1, 那么 总和=子代总和×2+子代情况总数+子代...总和 = 子代总和 \times 2 + 子代情况总数 + 子代...

不对劲，考虑以概率的眼光来看本题。

对于每一个阶段，每个点为 1 的概率都是一半，除了叶子结点会往上扩散恒定 0，所以 dfs 即可。

最后的结果是 每个点前缀权值和×2n−1每个点前缀权值和 \times 2^{n - 1}。

试下样例导向，分解 288=32×25288 = 3^2 \times 2^5，符合上述规律。