2018 Multi-University, HDU Day 7

Problem A

Solved by kblack. 01:47 (+2)

题意：给一个边上带颜色的无向图，走的边颜色变化一次花 1，求最短路。

题解：边上加个点，到两个端点距离为 1，一个点出去的同色边缩一下，因为距离都是 1，跑 bfs 就好了，卡常。。。

Problem B

Solved by ultmaster. 04:56 (+4)

题意：由 a 个 A，b 个 B，c 个 C 为周期的字符串，现在给出 $m$ 个位置的信息，让你反求 $(a,b,c)$，要求字典序最小。

题解：（跟官方题解完全不一样）首先枚举周期 $p$，我们要对 ABC 分别求模 $p$ 下最小的位置和最大的位置。朴素暴力会超时。考虑使用 bitset 优化（去年多校套路），按照 2 的幂，只需要 log 次合并即可。但问题是需要查最低位（bitset 有）和最高位（bitset 霉有）。于是需要自己实现一个 bitset。发生了一系列错误，勉强 AC。

另解：把 A，B，C 存在三个 vector 里，然后二分搜索即可。代码短一倍，而且非常好写。

左移 64 位会出现未定义行为，一定要小心！Reference

Problem C

Upsolved by zerol.

题意：支持以下操作

123 操作都是往一个集合中放入一个时间戳为 t 的对栈的操作

1. push v

2. delete v （删除最靠近栈顶的 v）

3. pop （不超过 5 次）

4. 对于给定的 t，把所有时间戳不超过 t 的操作按时间戳对一个空栈顺序执行，回答顶部元素。

v 不超过 5，操作保证合法，时间戳各不相同。

题解：对于每个 v 单独维护栈，询问栈顶就比较一下所有栈的栈顶的时间戳。pop 操作就相当于把询问的栈顶元素删掉。所以询问时依次考虑不超过 t 的 pop，每次删掉栈顶元素，最后回答栈顶元素，然后回滚这些删除操作。对于每个 v，开一棵线段树，维护某个时间点栈内的元素个数。如果询问某个时刻 t 前操作的栈顶元素的时间戳，设该时刻的栈内元素个数是 x，那么答案就是不超过 t 的尽可能大的栈内元素个数恰好是 x - 1 的时间戳 +1。为了求这个东西，首先将 [1,t] 区间在线段树上分解成不超过 log 个区间，然后从右往左考虑，如果这个区间内的最小值不超过 x - 1，那么一定能在这个区间内找到答案，所以多维护一个最小值就好了。

Problem D

Upsolved by kblack. (-2)

题意：$n$ 辆公交车，均匀概率地在一个时间点前到，如果 $T_i$ 还没到，就走路，公交车时间 $a$ 保证小于走路时间 $b$，求期望到家时间。

题解：两个部分，设 T 为最后等待的时间，最后走路的概率 $p = \prod_{i=1}^{n}{(1-\frac{min(L_i, T)}{m})}$，则假设公交也最后才开的期望时间为 $p \times (b+T) + (1-p) \times (a+T)$，然后减去公交车之前开的概率，这部分是$ \int_0^T {(1-\prod_{i=1}^{n}(1-\frac{min(L_i, t)}{m}))} dt$，这个要积的玩意儿是分段函数，最多分 $n$ 段，正确积分即可。

Problem E

Solved by ultmaster. 00:57 (+1)

题意：求 $\sum_{i=1}^m \sum_{i=1}^n \frac{\phi(ab)}{\phi(a) \phi(b)}$。

题解：$\frac{\phi(ab)}{\phi(a) \phi(b)} = \frac{\text{gcd}(a,b)}{\phi(\text{gcd}(a,b))}$。然后枚举 gcd，后面就是一个互质数对数经典的计数，反演即可。

Problem F

Upsolved by ultmaster.

题意：求小于 $2^n$ 的所有二进制上恰好有 3 个 1 的数构成的集合，有多少个集合异或和是给定数。

题解：显然我们不关心这个给定的数长什么样，我们只关心，这个数二进制上有几个 1。（也就是说 011 和 101 答案应该是相等的）理解这点非常重要，因为下面的 $f(i,j)$ 就是规定二进制上有 $j$ 个 1，然后假设它具有已知的形态（比方说 011）。

$f(i,j)$ 表示选了 $i$ 个，异或结果，恰好有 $j$ 个 1（选取必须不重复，并且不关心选取的顺序）。站在 $f(i,j)$ 的角度倒推，我们关心上一步是怎么来的。那么 $f(i,j)=f(i-1,j+3) \binom{n-j}{3} + f(i-1,j+1) \binom{n-j}{1} \binom{j}{2} + f(i-1,j-1) \binom{n-j}{2} \binom{j}{1} + f(i-1,j-3) \binom{j}{3}$。当然还需要对此结果进行修正，比如最后两步可能选了同样的东西，要减去 $f(i-2,j) \left( \binom{n}{3}-(i-2) \right)$（减去 $i-2$ 是以前选过的东西，由于 $f(i,j)$ 不关心选取的顺序，所以我们可以把可能重复的选择调换到第 $i-1$ 步再选，这样之前就没有重复的可能性）。最后还需要考虑当前选择顺序带来的额外贡献，除以 $i$。

Problem G

Upsolved by ultmaster.

题意：给一个黑白棋盘（左右连通，相当于圆柱形），每次翻转一个格子，或者一列，问有多少黑色连通块和白色连通块。

题解：BZOJ1453 增加了翻转一列和左右连通的设定。基本上原题上稍微改改（加个 5 行左右），就做完了。

首先要注意到连通块数目 = 总个数 - 连成森林需要的边数。

基本思路如下，维护一个线段树，每个叶子节点表示一列，在每个节点上维护一个 $2n$ 的并查集，$1$ 到 $n$ 表示这些列中最左边的一列的连通性状况，$n+1$ 到 $2n$ 表示最右边一列的连通性状况。然后 $n+1$ 到 $2n$ 可以往 $1$ 到 $n$ 的里面连（如果采用有向合并会给后面的处理带来便利）。还要在每个节点上维护两个数（连通块个数，表示答案）。合并的时候，父亲（母亲？）节点的连通块个数是两边的连通块个数加起来，然后对中间那两列进行合并，每一次有效的合并，都会让相应的颜色的连通块个数减 1。实现合并的时候可以将两边大小为 $2n$ 的并查集连起来组成一个大小为 $4n$ 的并查集，然后进行处理；处理完成后，不超过 $n$ 的部分就是我们想要的；超过 $3n$ 的部分，分两种情况：如果根节点不超过 $n$，则保留；否则要把根节点转移到超过 $3n$ 的中间（很有可能是自己，也有可能不是）。然后把这一部分平移到 $n+1$ 到 $2n$ 即可。

翻转一列的话，暴力翻转就好。左右连通的话，查询的时候，开一个 $2n$ 的并查集用上面的方法合并就可以了。

时间复杂度是 $O(qn \log n \cdot \alpha(n))$ 的。有点卡常，如果开两棵线段树可能会超时。但做了原题之后发现根本不用。

Problem H

Solved by ultmaster. 01:41 (+)

题意：给一个基环外向树，两种询问：改边权，求两点最短距离。

题解：把多的那条边拿出来分开考虑，剩下的就是一棵树。然后最短距离要么就是在树上走的，要么就一定经过那条边。两种情况讨论一下，剩下的就是一个 树链剖分 + 线段树经典套路。

Problem I

Solved by zerol. 01:26 (+1)

题意：给一棵树，每个点上都有一个标记，表示向上跳几步。要求支持：1. 修改标记的值。2.询问从 u 开始连续跳，直到跳出树外需要的步数。

题解：每个点向上跳若干步跳到的位置可以用倍增或树剖查询。如果每个点向能一次跳到的点连边，那么这就是一棵树（还需要加一个点表示树外）。那么问题就转化成了换父亲，询问链上的距离。这部分用 LCT 维护，因为要询问距离需要维护一个 size。

Problem J

Solved by kblack. 00:43 (+1)

题意：$\left\{\begin{eqnarray*} F_1 &=& A \\ F_2 &=& B \\ F_n &=& C\cdot{}F_{n-2}+D\cdot{}F_{n-1}+\left\lfloor\frac{P}{n}\right\rfloor \end{eqnarray*}\right.$ 给定 A, B, C, D, P, n 求 $F_n$。

题解：$\lfloor{\frac{P}{n}}\rfloor$ 只有 $\sqrt{P}$ 种，分段快速幂就好了，注意分段的间隔。

Problem K

Solved by zerol. 02:04 (+)

题意：有 k 维属性，对于每个怪物，如果每一维属性都大于等于它的话，就可以击败他，然后每一维属性都增长一个非负整数。求最后能击杀的怪的数量和最后属性值。

题解：怪物肯定能杀就杀。对于所有怪物，按照每一维从小到大排序，用 k 个指针维护当前这一维属性能被击败的怪并标记，一旦一个怪物被标记了 k 次就挂了。