某岛

… : "…アッカリ~ン . .. . " .. .
July 29, 2020

BOI 2020

BOI 2020

Day 1

传送门
HackMD
竞プロ日常

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 的时候跳过了无穷的情况,原理就跟一些矩阵乘法的题目,需要优化掉内层循环的取模差不多。

然后 BenQjiangly 的给都是 Dijkstra 正解。最猛的是 liouzhou_101,直接卡时,居然还卡过去了 Orz。。。(所以我也卡时吧。。> <。。。