\(6\) 题只做出来 \(1\) 题，损失惨重

A. Dalton the Teacher

显然，答案一定和最初的不满意人数有关，所以输入的时候统计一下

然后，将不满意的人的座位 每两个人交换一次 即可，交换次数就是答案

如果不满意人数是奇数，那么答案还要加 \(1\)

时间复杂度 \(O(n)\)（输入的复杂度）

B. Longest Divisors Interval

md考场上本来想到正解了，结果复杂度估错了，怕被扣 \(50\) 分所以就没写出来

结论：最长的合法区间一定是形如 \([1,r]\) 的

个人理解就是，因为越到后面的数字质因子越多，但是对于 \(n\) 来说质因子越少的数越优（就是越容易整除 \(n\)）

所以直接从 \(1\) 开始枚举，计算出第一个无法整除 \(n\) 的数字 \(x\)，答案就是 \(x-1\)

实际时间复杂度是 \(O(\log n)\)，我考场上算成了 \(O(\sqrt{n})\)，这应该是最坏情况下的复杂度，但这种情况的 \(n\) 似乎很少

C1. Dual (Easy Version) & C2. Dual (Hard Version)

直接说 Hard 版本，因为 Hard 版本的思路可以向下兼容到 Easy 版本

这题可以分类讨论

如果只有正数或 \(0\)，显然可以直接做前缀和；只有负数或 \(0\) 就是做后缀和。这样的操作次数是 \(n-1\)，最多操作 \(19\) 次
如果正数和负数都有，我们可以将其转化为上面的情况 \(1\)。因为 SPJ，不是求最小操作数，那么操作越多就越有利于我们的转化

因为情况 \(1\) 就要用掉最多 \(19\) 次操作，Hard 版本限制我们最多用 \(31\) 次操作，这时就只剩下 \(12\) 次操作供我们进行转化

继续考虑分类讨论

①如果 \(|\max_{i=1}^n a_i|>|\min_{i=1}^n a_i|\)（即正数最大值的绝对值大于负数最小值的绝对值），记 \(maxn=\max_{i=1}^n a_i\)，我们可以把 \(maxn\) 加到所有的负数上，这样就可以转化成情况 \(1\)。但是，这样做要保证负数最多有 \(12\) 个（因为只能通过 \(12\) 次操作来转化）

那么负数超过 \(12\) 个怎么办？我们发现，对于任何一个数，自己加自己的值其实就是 \(\times 2\)

那么设对数字 \(x\) 进行自加 \(y\) 次的操作，则：\(x\leftarrow x\times 2^y\)，而最大的负整数是 \(-1\)，它只需要自加 \(5\) 次就会小于 \(-20\)（\(-1\times 2^5=-32\)），这时再把它加到剩余的正数上，就会用不超过 \(7\) 次的操作转化为情况 \(1\)（因为这时负数个数至少为 \(13\)）

②反之亦然

所以这题就解决了

D. Earn or Unlock

考虑朴素做法，其实类似 0/1背包,令 \(dp_{i,j}\) 表示操作到第 \(i\) 个数字已经解锁了后面 \(j\) 张牌的情况是否成立，不难看出 \(j\) 超过 \(n\) 就没有意义了，所以我们只需枚举到 \(2n\) 即可，暴力 DP 复杂度为 \(O(n^2)\)

然后用 bitset 优化就可以把复杂度优化到 \(O(\frac{n^2}{w})\)，可以卡过去

E. Expected Destruction

显然期望 DP，考场上写了个记搜结果样例都没过

如果直接讨论，因为题目主体是集合操作，所以会显得有些抽象；把集合转化成一个 \((n+1)\) 行，\((m+1)\) 列的矩阵，其中第 \(i\) 行，第 \(S_i\) 列处有一个方块，对这个方块进行操作就是让其移动到同行的第 \(S_i+1\) 列上，如果这一列上早已存在一个方块，就将后一个移动的方块消除；为了让到达第 \(m+1\) 列的方块也能直接消除，第 \(n+1\) 行，第 \(m+1\) 列上会存在一个方块

这样，问题就变成了一个移动方块的问题

所以，如果所有方块都在 m+1 列中，则该集合为空，即到达最终结果

考虑计算一对相邻方块，他们到达同一列的期望时间

设 \(dp_{i,j}\) 表示方块 \(x\) 在第 \(i\) 列且方块 \(x+1\) 在第 \(j\) 列时，这两个方块到达同一列的期望时间

边界：