2018 Multi-University, HDU Day 5

卡常卡得真刺激。

kblack: 按去年青岛，35 个金，三题手速金，传奇再现。

zerol：零贡献。被 TLE 和 MLE 搞自闭了。

Problem A

Upsolved by kblack.

题意：给一颗仙人掌，求 $\sum_{1 \leq s < t \leq n}{\left(s \oplus t \oplus \mathrm{flow}(s, t)\right)}$。

题解：讨论环，环上最小值一定是切边（如果环需要切），不妨删掉这条边，其他边加上他的流量，这样就变成树上问题了，树上是经典问题，按边大小从大到小枚举合并即可，注意答案超大，要 ULL。

Problem B

Solved by ultmaster. 01:15 (+)

题意：求一个数的所有只需要交换 $k$ 次以内的排列中，最小的和最大的。

题解：暴搜一下就好了。

看了题解以后的补充：题解是傻逼，只要从第一位还是 DFS 下去，每一位枚举用后面哪个位置换上来就可以了。这种 DFS 基于如下假设：肯定可以在 9 次交换之内达到任意状态（每次选的时候都选到正确的东西就好了）。非常好写。复杂度也是 $O(n!)$。

Problem D

Upsolved by zerol. (-10)

题意：询问到 u 和 v 距离均不超过 d 的点的个数。强制在线。

题解：设 f(u, d) 是与 u 距离不超过 d 的点的个数。那么答案是 f(u, d) + f(v, d) - f(mid(u, v), d - dis(u, v) / 2)。考虑到奇数的问题，边上都加一个点。关于在线求 f(u, d) 是动态点分治的经典问题（注意点分树上的点的最大深度之和是线性的，所以每个点开一个深度大小的数组求前缀和而不是插入深度后二分）。但是睿智的出题人认为两倍的点是不能体现技术的，所以要卡掉。不开两倍点，考虑偶数的情况，设中间两个点是 x 和 y，要求距离 x 或 y 不超过 d-dis(u,v)/2（下取整） 的点的个数。在点分树上 x 和 y 都从根往下爬，如果它们属于同一棵点分树子树 u，那么就不重复计算，就考虑与 u 不超过 D - min(dis(x, u), dis(y, u)) 的点，注意减掉 u 的直接儿子的子树中的情况时深度要按新的二合一深度计算。

zerol：又是 MLE 又是 TLE。MLE 逼我把倍增 lca 换成了树链剖分，还把指针换成了数组下标。在开两倍点的情况下，两个 log 本地 16s，一个 log 本地 11s，杭电就是 T，T 到我优化不动了。可见出题人精确的卡常技术，不得不服。

Problem E

Solved by ultmaster. 00:49 (+)

题意：求一个圆挖掉若干个小圆，剩下的部分的周长。

题解：计算几何签到。判完圆的位置关系后，求交点，然后判断交出来的弧是优弧还劣弧（通过圆心连线的向量应该加在交点之间来判断）。因为 位置关系搞不清楚，调了好久。

另解 (by csl)：让我们回顾一下余弦定理。

Problem F

Upsolved by ultmaster.

题意：用最少的链覆盖一个超立方体偏序集，超立方体每一维是 $1$ 到 $p_i$。

题解：官方题解讲得很好。补充几点：1. 关键在于要剔除掉和大于 $M$ 的那些东西（所以需要滑动窗口）；2. 什么东西要模，什么东西不要模，一定要严格区分；3. 多项式可以用一个类似于背包的东西求，求完之后两边做积，其中一边用前缀和优化；4. 尝试使用 vector 编程见鬼了好久。

Problem G

Solved by kblack. 00:57 (+)

题意：区间覆盖线段树，修改巨多，离线询问点值。

题解：一个区间按 ST 表拆成两个，按 ST 表更新反方向贡献回去就好了。

Problem H

Solved by ultmaster. 04:27 (+5)

题意：求一个序列中最长的形如 012365436789 的子序列。

题解：一看就是 DP，关键在于如何设计优秀的状态。区间 DP 大概是不大行的。我们考虑前缀。我们可以暂时不考虑后面的 6789，先考虑前面的这一部分的前缀，为了判断下一项最优是多少 / 可不可行，我们需要记住多少信息？比如对于 0123654，我们需要记住的是这个 3 和这个 6；比如对于 012，我们需要记住的是 2 而且没有碰到拐点。这样的话，很容易发现只要记住两维的信息（$10 \times 11$，第二维还有一个不存在的状态），我们就可以推出下一个数字可不可行了。

形式化地说，记 $f(i,j,k)$ 为到第 $i$ 项为止，这一项必选，拐之前的那个数是 $j$，拐之后的那个数是 $k$，所能得到的最长答案。那么：

• 若 $k=-1$，对于 $c \ge a_i$，用 $f(i,j,k)+1$ 更新 $f(nxt(i,c), c, k)$（继续上升）和 $f(nxt(i,c), j, c)$（把 $c$ 当作拐点）。
• 若 $k \ne -1$，对于 $j \le c \le a_i$，用 $f(i,j,k)+1$ 更新 $f(nxt(i,c), j, k)$（已经拐了就只能下降了，但是也不能比拐之前的高度还要低）。

其中 $nxt(i,c)$ 表示 $i$ 位置之后下一个出现 $c$ 的位置。这样的话我们成功地算出了形如 01236543 的情形。

接下来还要接一段，只要预处理一下后缀的上升子序列的情形（从后往前更新，倒过来看就是下降的），那么对于所有 $f(i,j,k)+suffix(i,k)$ 都刷一遍答案就好了。

复杂度 1E8 刚好是满的。一定要注意初始化！初始化细节留给读者思考。

Problem J

Unsolved. (-5)