2018 Multi-University, HDU Day 3

Problem A

Solved by kblack. 01:45 (+5)

题意：在长度为 $n$，部分随机的序列中，求大小为 $m$ 的滑动窗口滑过的每个区间的最大值及最大值变化次数。

题解：从后往前即可获得每个数的下一跳，再正着并查集维护即可。辣鸡出题人卡常，体验极差！

Problem C

Solved by ultmaster. 00:53 (+)

题意：若干加边删边操作，每次操作后，询问图中 $1,2,\ldots,n/2$ 匹配的数目。

题解：由于 $n$ 很小，维护每一个子图 ($2^n$) 的匹配数目。加边的时候，把含有那条边的子图都加上去掉那条边的子图的部分的现有的值。删边同理。

ultmaster: 总觉得有什么地方不大对，但出乎意料地输出了正确的答案。（运气真好）

Problem D

Solved by ultmaster. 00:17 (+)

题意：求第 $k$ 个欧拉函数是合数的数。

题解：经典的打表找规律签到。

Problem F

Solved by zerol. 00:26 (+)

温暖的签到。

Problem G

Solved by ultmaster. 02:27 (+)

题意：给一些点，让你选其中一些点，从左到右，然后和 $(0,0)$ 组成一把扇子，使得扇子的有向面积最大。

题解：其实就是求一个上凸壳。魔改凸包的单调栈即可。注意本题要求输出字典序最小，还会有重点。不过都是小问题，稍微注意一点不会写错。

Problem H

Upsolved by ultmaster.

题意：经典月赛题大鱼吃小鱼又来了。现在有一棵树，要求吃的顺序满足树的偏序。

题解：像大鱼吃小鱼那样排序，然后注意到两件事情

1. 如果排在最前面的正好是树的根，那么直接拿走;

2. 如果不是，那么吃完这个东西的父亲之后一定直接吃它，所以可以把这个节点和它的父亲合并，用并查集和 set 维护即可。

两件事情都把 $n$ 的问题变成了 $n-1$ 的子问题。

以上基本把题解朗读了一遍。补这题的时候有点不在状态，蛋疼了好久。

1. 偏序里面有个地方忘了 return（为什么没警告啊）。 2. int 改 LL 改了一半，WA1。

另外合并的时候式子如下：

$father.a_{new} = \max(father.a, father.a - father.b + victim.a)$. $father.b_{new} = victim.b - victim.a + father.b - father.a + father.a_{new}$.

Problem I

Solved by kblack. 03:24 (+4)

Problem J

Unsolved. (-2)

Problem L

Solved by kblack. 00:22 (+)

Problem M

Solved by zerol. 03:40 (+)

题意：给一个有向图，每次询问从 u 到 v 至少经过 k 条边的最短路是多少。

题解：考虑 M[k] 是一个 n*n 的矩阵，表示恰好经过 k 条边的每两个点之间的最短路。可以用 $O(n^3)$ 的代价由 M[a], M[b] 计算出 M[a+b]。对于询问 u, v, a+b，可以用 O(n) 的时间从 M[a] 和 M[b] 计算得到。所以取 k 的最大值的平方根 100，计算 k = 1,2,...,100,200,300,...,10000 的时候的 M[k]。最后还有一个问题就是把恰好 k 条变成至少 k 条，方法就是计算 k=1,2,...100,101,...150 的 M[k] 并向前依次取 min，因为至少 k 条边的最优解的经过边数不会超过 k+n（否则必定成简单环可删去）。