讲题人：你看第一个(棒棒糖)表情和第三个(爱心)多像，所以你发第一个我就当成第三个了
(为什么你qq的性别是女呀)这需要解释什么吗？
啊？这不严谨吗？你们先下课，我先想想怎么证。
这是咱们的 OI 教学工具(指 MC)，不是别的。
你们不要在台下偷偷使用神秘小工具啊。
哇，大部分同学都看懂神秘小工具了，太好啦。
hyw。
扣咦，不准扣糖，不准扣糖！
A.Two Different
先考虑 \(n=2^k\) 的情况，那么两两一组，然后再对组进行两两分组，重复此过程，结果一定是一个数。
对于任意 n，找到小于它的最大的 \(2^k\)，先对前面做一次，再去后面的 \(2^k\) 再做一次。
B.Nauuo and Portals
直接做显然是抽象的。
可以发现每一次传送相当于一次交换，所以就是通过一些交换，得到两个目标序列。
设置一个要求，后放的不能影响先放的，第 i 次把 i 全部归位。
假设在第 p 列和第 q 行，就在 \((i,p),(q,i)\) 放一个。
C.Valentine
对每一行先加上 \(i*n\)，这样所有列都满足。
先弄出来一个最大的正方形，使得列的贡献恰好不超过 n，然后进行调整。
考虑对每一行进行操作，将一部分弄成递增序列，可以证明一定存在解。
D.Urban Planning
固定一个矩形大小，然后从右下角开始贪心。
用一个队列不断扩展可选位置，能够快速的减到差不多 1e6，这东西的衰减速度大约是 \(O(n^2)\)。
接下来就是取一个部分，然后往上取，这样每次大概减少 \(O(n)\) 级别。
最后剩下一个 \(O(n)\) 级别的东西从左上角 dfs 就行了。
E.Connected Cubes
考虑什么情况下能联通，如果将列拆开，那么只需要在每列之间放上每种颜色，就一定联通。
考虑如何拆开，每次可以把一行连出去，然后把其他垫高一层，这样就能分开了。
F.Keep Perfectly Matched
先考虑判定问题，从一个叶子出发，按照匹配 -> 非匹配的过程走，一定会走到一个叶子，同时删掉就一定满足。
考虑最大贡献，对于每条边，经过它的次数一定是两个子树中较小那个的大小。
考虑以重心为根，此时每条边的贡献一定是子树大小，因为每个子树大小都不超过 \(\frac{n}{2}\)。
考虑构造，每次让最大的子树拿出一个点，和子树外去匹配。
注意到任意一个点都一定能走到，然后优先队列维护一下就行了。
G.Sum
这东西猜结论一定是一堆选满，一个选一部分一堆不选。
感性证明如果两个都取一部分，那么一定存在一个序列的最后一个元素大于另一个，此时把这个取完显然是优于各取一部分的。
接下来是背包，但背包合并的复杂度显然无法接受。
可以用一个叫缺一分治的东西，目前分治到 \([l,r]\) 表示这个区间还没取。
这样依次插入左边然后递归右边或插入右边递归左边，时间复杂度 \(O(nk\log n)\)
H.鱼类考古学
先加一定是不优的。
一定是划分成 k 个集合，集合内先与然后再求和。
对每一位进行考虑，如果有两个集合同时有 0，那么一定分开更优。
当 1 的数量 \(\le k\)，1 尽量每个占一个，然后递归子问题。
\(>k\) 时 0 应该放在同一个集合内，然后结果为按位与，对 1 继续分治下一位。
I.(ox)
首先发现 o 时没有用的，x 只能放在合法括号串之间。
在括号序合法的时候，移动 x 一定是不优的，因为只需要把 1-2 个括号移动就能满足所有。
所以 ox 是不会移动的，移动次数就是逆序对数。
对于一个非法括号串，要同时用最少步数把它弄成合法串。
设 \(f_{i,j}\) 表示当前在括号序的第 i 位，ox 的第 j 位，前缀和一下就行了。