\(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\) 列时，这两个方块到达同一列的期望时间
边界：
-
\(dp_{i,m+1}=m+1-i\)（因为只有方块 \(x\) 可以移动）
-
\(dp_{i,i}=0\)（因为方块 \(x\) 已经与方块 \(x+1\) 同一列）
转移方程：
\(dp_{i,j}=\frac{dp_{i+1,j}+dp_{i,j+1}+1}{2}\)
答案就是 \(\sum_{i=1}^{n-1} dp_{S_i,S_{i+1}}\)
F. Michael and Hotel
交互题，题解看不懂
标签：12,题解,889,负数,方块,操作,Div,复杂度,dp From： https://www.cnblogs.com/cantorsort2919/p/17591400.html