BOI 2020
Table of Contents
Day 1
Problem A. Colors
题意
交互式问题，给定 n，每次你可以将头发染成 1-n 中间的一个数字，如果相邻两次的数字差的绝对值 >= C，那么男朋友会注意，返回 1，否则返回 0。每个颜色只能用一次，用尽可能少的询问找到 C。
题解
很优雅的倍增构造。
Problem B. Mixture
题意
动态维护若干瓶调味料，每瓶调味料中装有一定质量的 盐，胡椒与大蒜 的混合物，给定美食家最喜欢的调味料的组成，每次询问，可以增加一瓶新的调味料或者删除一瓶之前添加过的调味料，返回至少需要几瓶可以混合出美食家最喜欢的口味。
题解
不会。
Problem C. Joker
题意
给定一张有 n 个点 m 条边的无向图，每次询问给出一个区间 [L, R]，问是否存在奇环，使得环中不包含区间中的点。
题解
是否存在奇环，等价于二分图判定。静态可以 dfs，动态的话可以 dsu，最后外面套一层莫队算法即可。
当然也可以直接用 lct！
对于删除 [l, r] 区间的边，我们可以用类似破环为链的方法，转化为每次询问保留 (r, l+m) 区间的边，显然边越少越容易合法，满足单调性。我们按照时间顺序依次插入所有边，用 double-point 维护出处理到时间 r 时，最大的 l 使得当前的状态合法即可。这样就可以贴 BZOJ 4025 的代码了。
Day 2
Problem A. Graph
题意
给定一个边被红、蓝染色的无向图，求一组节点的权值方案，满足对所有的红边，关联的节点的权值和为 1，对所有的蓝边，权值和为 2，满足条件的基础上，最小化所有节点的权值和。
题解
让人想起了之前 Atcoder 上的一道染色的题。不过这个题是实数。做法是随便找个点和初始标记一路 dfs 下去把每个节点标记成 ax+b 的形式，其中 a 属于集合 {-1, 0, 1}，x 是一个待定系数，最后算出 x 的值即可，需要一些 insight。
Problem B. Village
题意
给定一个树，求两组错位排列的方案 P，分别使得 \sum dist(i, P[i]) 的权值和最大和最小。
题解
首先最小的话显然尽可能交换相邻的结点编号就好了，我们就每次找叶子，如果没有交换过，就和父节点交换，这样最后有可能还剩一个，没关系随便找一个相邻结点再交换一次就好。
对于最大的情况，我们考察每条边 (u,v)，那么这条边贡献的上界是 min(sz[u], sz[v])，我们发现可以构造方案让所有边的上界都达到，方法是只要考察重心，让每个点都标记在另一颗子树中即可。
这样看的话，似乎是需要找一下重心的。。。但是 最快的提交代码 直接就上了。。只要证明这样构造之后，可以找到一个节点作为根，使得每个节点都不落入同一子树中就行了。。而这是显然的，因为以重心分割的话，子树的 size 不会超过 n/2。
Problem C. Viruses
题意
基因序列是一个由 n 种数字形成的字符串，其中 0、1 为终止字符，其他为病毒字符，给定一张基因突变的表格，每个表格表示一个病毒字符可能会突变成的基因串，一个基因序列每一秒中，会有一个病毒字符突变，一些病毒字符可能有多种突变方向。给定一些模式串作为抗体，问每个病毒字符所能形成的最短的，不被任意一个抗体所识别的终止序列的长度（或者输出不存在）。
题解
没有病毒串的时候显然可以用类似最短路的方法 dp 出最短长度。。有病毒串的时候开个自动机就好。。由于我们需要支持合并字符串的操作，所以 dp 状态需要加维，记录在自动机中的状态区间，具体说来就是 dp[i][st][ed] 表示基因 i 展开之后，从状态 st 到状态 ed 的最短路径长度。
冲了一发 果断 TLE 了。虽然本质上是最短路模型，但是本题的边是广义的，可能会与多个节点关联，Dijkstra 着实不太好写，所以用了 Bellman_Ford，考虑到瓶颈主要在松弛（Relax）操作上（每次都要跑一遍神似 Floyd 的 DP），感觉改成 SPFA 可过。
换了 SPFA 之后还是有一个点过不去，看来本题数据还是很良心的。。
看了一下其他人的搞法，最快的 WZYYN 同学非常厉害，直接 Bellman_Ford 加了一个奇怪的剪枝就过了，然后 duality 看起来是常规的 SPFA，在 Relax 的时候跳过了无穷的情况，原理就跟一些矩阵乘法的题目，需要优化掉内层循环的取模差不多。
然后 BenQ 和 jiangly 的给都是 Dijkstra 正解。最猛的是 liouzhou_101，直接卡时，居然还卡过去了 Orz。。。（所以我也卡时吧。。> <。。。）
