# 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)）