因为有的题代码没写 所以统一不给出代码了。
感觉题目整体还是很提高组的 就是我 12 天比赛放在 3h 打就死了
COVID19
直接枚举第一个感染的是谁 模拟一下就好了。按照实现情况 $O(n^2)/O(n\log n)$
CORUS
按照题意贪心模拟一下就好了。
TRPLSRT
首先把排列拆成若干个轮换，轮换是有顺序的（$i \to p_i$）目标是拆成 $n$ 个轮换。
对于每个长度 $>3$ 的轮换 任意找三个连续的点 按照轮换的顺序的逆方向指定 就可以让两个点变成大小为 $1$ 的轮换，这也是最优方案。
对于长度 $=3$ 的轮换，按照轮换反方向操作可以直接变成三个大小为 $1$ 的轮换。
对于长度 $=2$ 的轮换，只能和另一个 $=2$ 的轮换配对后 $2$ 步一起消去。
按照大小从大到小排序 挨个处理就行了。如果无法完成 $2$ 之间的配对就无解。
CHANDF
如果没有上下界限制和最小化限制的话 显然全填 $1$ 最优。
如果没有上下界限制 要求最小化答案的话 如果一个位 $X,Y$ 都是 $0$ 的话那么这个位就没必要填 $1$ 了。
如果只有上界限制的话 可以枚举卡到上界哪一位 相当于后面可以随便选。
如果上下界都有限制的话 需要枚举是否上下界都卡这一位 只卡上界 只卡下界 都不卡 分别暴力枚举就行了。
Bouns1：按位或
只有两边全是 $1$ 才要填 $0$ 否则都填 $1$ （正好反过来）
Bouns2：按位异或
我也不会 求评论区大佬教我（或者直接私聊我 QQ）
UPD at 2020/6/10
突然想起来山东队长 suncongbo 教育我一种新做法
其实关键问题在于固定某些位后无限制的位咋做 接下来用$(a,b)$表示二进制某一位上 $A$ 的数是 $a$ ，$B$ 是 $b$。
如果 $(0,0)$ 我们对着填 $0$
如果 $(1,1)$ 我们对着填 $1$
如果 $(0,1)$ 或者 $(1,0)$ 呢？我们发现无论填 $0$ 或者填 $1$ 他们的和都是不变的 于是我们接下来要最小化差（这个看起来很自然的结论我总是想不起来）
具体来说 我们找到第一个这样的位置调整为 $1$ 剩下的都调整为 $0$ 就好了。
SORTVS
先入为主地想错了这题。
这个题目相当于要求你把排列 $p$ 排序。
首先我们将免费交换看成边建一个图
只需要证明树可以调整好就能证明上述结论是对的。观察一个点连续在一条链上交换 相当于只是这个点和链的末尾交换。所以我们考虑从根开始 肯定有偶数个点满足自己的目标点和自己不在一个子树里（显然）所以就交换一下 递归做即可。
我们考虑将 $(i,p_i)$ 看成原图中的有向边。我们发现如果这两个点在同一个连通块里就不用担心了。只需要考虑这两个点在不同连通块的情况 所以我们对每个连通块内部缩点 用$(i,p_i)$ 这些边建一个新图。
我们每次交换只能找出一个环然后消掉。不如考虑我们每次找出一个简单环 这样就能省下 $1$ 的代价 这也是最优的方案。具体操作还是考虑每交换相邻的两个点就会将一个点清出环 这样只需要环长-1 次就可以了。
于是我们相当于要给这些边配对 使得环尽量多。这里各种贪心其实都是错的（并且题目都这么小范围直接状压不好么）
我们考虑状压 dp：设 $f_S$ 表示 $S$ 集合内的边最多能凑成多少个环。初始化如果 $T$ 构成一个简单环 那么 $f_T = 1$。
转移直接枚举一个集合分开就好了。这样复杂度是 $O(3^n)$ 的。
其实可以通过每次枚举一个环转移做到更优。
NBOTS
竟然是 Challenge 题 那么说明我肯定不会。
题解说搞个估价函数随机化就能拿到很高的分，我也不清楚。
但还是讲一下如果计算快速消去一行的代价吧：这是个区间 dp 设 $f[i][j]$ 表示剩下 $[i,j]$ 的代价 枚举下一次如何操作即可。
NRWP
每个点可以选择正负 并且只有 $200$ 个点 想到最小割。
如果两个点在不同集合内就会产生 $p_ip_j$ 的代价。如果某个点在某个集合内会产生某些代价。网络流板子拉一拉就好啦。
TWOSTRS
考虑答案只有可能是 $A$ 的前缀和 $B$ 的后缀组成。
所以我们去枚举所有可能的情况 接下来是去考虑如何快速计算。
分为三段：
- 只在 $A$ 里面，可以预处理
- 跨过了 $A$ 和 $B$ 的拼接点，可以考虑先对所有小串建出 AC 自动机 AC 自动机上当前位置对应的点是一段后缀 所以我们直接定位到 $A$ 当前前缀对应的点 然后扫过去 $B$ 的最多 $25$ 个字符 统计一下每个点的子串的和就好了（fail 树上到祖先的和）
- 注意到这样会把 $B$ 算掉一部分 要去掉这一部分。
还是对 AC 自动机理解不深（忘了） 实际上每个点对应的是一段最长可接受的后缀。
