# BOI 2020 [toc] # Day 1 [传送门](https://codeforces.com/contest/1386) [HackMD](https://hackmd.io/@E-5gxTGiSByBOKpvsaKa_g/HJDNb1Aev) [竞プロ日常](https://t.me/algorithm_daily_of_minako/382) ## 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](https://github.com/lychees/ACM-Training/tree/master/Archive/BZOJ/4025%20%E4%BA%8C%E5%88%86%E5%9B%BE) 的代码了。 # Day 2 [传送门](https://codeforces.com/contest/1387) [竞プロ日常](https://t.me/algorithm_daily_of_minako/377) ## 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])`,我们发现可以构造方案让所有边的上界都达到,方法是只要考察重心,让每个点都标记在另一颗子树中即可。 这样看的话,似乎是需要找一下重心的。。。但是 [最快的提交代码](https://codeforces.com/contest/1387/submission/87770865) 直接就上了。。只要证明这样构造之后,可以找到一个节点作为根,使得每个节点都不落入同一子树中就行了。。而这是显然的,因为以重心分割的话,子树的 size 不会超过 n/2。 ## Problem C. Viruses ### 题意 基因序列是一个由 n 种数字形成的字符串,其中 0、1 为终止字符,其他为病毒字符,给定一张基因突变的表格,每个表格表示一个病毒字符可能会突变成的基因串,一个基因序列每一秒中,会有一个病毒字符突变,一些病毒字符可能有多种突变方向。给定一些模式串作为抗体,问每个病毒字符所能形成的最短的,不被任意一个抗体所识别的终止序列的长度(或者输出不存在)。 ### 题解 没有病毒串的时候显然可以用类似最短路的方法 dp 出最短长度。。有病毒串的时候开个自动机就好。。由于我们需要支持合并字符串的操作,所以 dp 状态需要加维,记录在自动机中的状态区间,具体说来就是 `dp[i][st][ed]` 表示基因 i 展开之后,从状态 st 到状态 ed 的最短路径长度。 [冲了一发](https://codeforces.com/contest/1387/submission/88233757) 果断 TLE 了。虽然本质上是最短路模型,但是本题的边是广义的,可能会与多个节点关联,Dijkstra 着实不太好写,所以用了 Bellman_Ford,考虑到瓶颈主要在松弛(Relax)操作上(每次都要跑一遍神似 Floyd 的 DP),感觉改成 SPFA 可过。 换了 SPFA 之后还是有一个点过不去,看来本题数据还是很良心的。。 看了一下其他人的搞法,最快的 [WZYYN](https://codeforces.com/contest/1387/submission/87771947) 同学非常厉害,直接 Bellman_Ford 加了一个奇怪的剪枝就过了,然后 [duality](https://codeforces.com/contest/1387/submission/87781698) 看起来是常规的 SPFA,在 Relax 的时候跳过了无穷的情况,原理就跟一些矩阵乘法的题目,需要优化掉内层循环的取模差不多。 然后 [BenQ](https://codeforces.com/contest/1387/submission/87793448) 和 [jiangly](https://codeforces.com/contest/1387/submission/87776530) 的给都是 Dijkstra 正解。最猛的是 [liouzhou_101](https://codeforces.com/contest/1387/submission/87788401),直接卡时,居然还卡过去了 Orz。。。([所以我也卡时吧。。> <。。。](https://codeforces.com/contest/1387/submission/88237324))