Difference between revisions of "2018 Multi-University, HDU Day 5"

From EOJ Wiki
Jump to navigation Jump to search
 
(23 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
卡常卡得真刺激。
 
卡常卡得真刺激。
 +
 +
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 ==
 
== Problem B ==
  
 
Solved by ultmaster. 01:15 (+)
 
Solved by ultmaster. 01:15 (+)
 +
 +
题意：求一个数的所有只需要交换 $k$ 次以内的排列中，最小的和最大的。
 +
 +
题解：暴搜一下就好了。
 +
 +
看了题解以后的补充：题解是傻逼，只要从第一位还是 DFS 下去，每一位枚举用后面哪个位置换上来就可以了。这种 DFS 基于如下假设：肯定可以在 9 次交换之内达到任意状态（每次选的时候都选到正确的东西就好了）。非常好写。复杂度也是 $O(n!)$。
 +
 +
== Problem C ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意：给了一堆基础知识，包括分圆多项式的定义，让你分解 $x^n-1$。
 +
 +
题解：官方题解不知道它在讲什么。
 +
 +
<math>\Phi_n(x) = \prod_{1 \leq k \leq n, \gcd(n, k) = 1}{\left(x - {w_n}^k\right)}</math>。两边取 log 之后是经典的莫比乌斯。化简的时候要用到著名的结论 <math>x^n-1 = \prod_{1 \le k \le n} \left(x - e^{2 \pi i k / n} \right)</math>。化出来结果应该是 <math>\prod_{d|n} \left(1 - x^{n/d} \right)^{\mu(d)}</math>。
 +
 +
''Comment:'' 其实你盯着结果看的话是一眼能看出来的，反演一步就能得到 $\Phi$。
 +
 +
然后 $\mu$ 的值显然只能是 -1 和 1，这个东西就和背包问题很像很像，唯一的问题是 -1 的时候不好办：使用著名的生成函数结论 $\frac{1}{1-x}=1+x+x^2+\cdots$ 转化成无穷背包就好了。官方题解里说这是一个模 $\phi(n)+1$ 的多项式（''我感觉在胡说八道''）。只是因为预知了超过 $\phi(n)$ 的项最后都不会用到，'''而且计算过程中永远是从前往后推，高阶项的值在任何时候都不会对低阶项产生影响，'''所以我们可以安全地忽略他们。（如果是模的话事情反而麻烦了，就是因为看了题解的这句话才陷入了思维的怪圈想了好久。）
 +
 +
至少题解中的复杂度分析是有道理的。该算法复杂度正确基于下面的事实：$\sum_{d|n} \phi(d) = 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 到我优化不动了。可见出题人精确的卡常技术，不得不服。虽然喷了，但这题还是不错的，增加了对点分树的认识。
 +
 +
zerol：可以发现，其实还是求了一次到两个点距离不超过 d 的点的并，虽然这两个点是相邻的。那么也许你想问，既然可以求并，为什么不直接求原问题的答案呢？因为相邻的点在点分树到根的路径最多只有一位之差，如果不相邻可能会差好多，导致虽然不是属于同一棵子树也会有重复计算。
  
 
== Problem E ==
 
== Problem E ==
  
 
Solved by ultmaster. 00:49 (+)
 
Solved by ultmaster. 00:49 (+)
 +
 +
题意：求一个圆挖掉若干个小圆，剩下的部分的周长。
 +
 +
题解：计算几何签到。判完圆的位置关系后，求交点，然后判断交出来的弧是优弧还劣弧（通过圆心连线的向量应该加在交点之间来判断）。因为 位置关系搞不清楚，调了好久。
 +
 +
另解 (by csl)：让我们回顾一下余弦定理。
 +
 +
== Problem F ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意：用最少的链覆盖一个超立方体偏序集，超立方体每一维是 $1$ 到 $p_i$。
 +
 +
题解：官方题解讲得很好。补充几点：1. 关键在于要剔除掉和大于 $M$ 的那些东西（所以需要滑动窗口）；2. 什么东西要模，什么东西不要模，一定要严格区分；3. 多项式可以用一个类似于背包的东西求，求完之后两边做积，其中一边用前缀和优化；4. 尝试使用 vector 编程见鬼了好久。
  
 
== Problem G ==
 
== Problem G ==
Line 20: Line 80:
  
 
Solved by ultmaster. 04:27 (+5)
 
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 I ==
 +
 +
== Problem J ==
 +
 +
Upsolved by zerol. (-5)
 +
 +
题意：某人从 A 中选了一个子串 B。他会回答你问的是非题，问最优情况下期望几次能够猜出 B。
 +
 +
题解：如果我能知道 A 中恰好出现了 k 次的子串共有 c 个，那么再建一个哈夫曼树就好了。但是数据范围比较大，要求是线性的算法。统计子串用后缀自动机（很可惜，内存不够）或者后缀树（由后缀数组构建，当然这个后缀数组也要线性求）。由于 $\sum k c = \binom{n}{2}$，所以对于入队（伪·优先队列）的分两种情况，如果不超过 n，在数组中合并累计，超过 n 入队列（注意不是优先队列）。数组中的扫一遍就好了，最后队列中有从小到大不超过 n 个元素而且范围是 n+1~2n，这是可以把队列当优先队列用，每次从头上取两个放入尾部（没错，就是单调的），然后就好了而且保证了线性复杂度。
 +
 +
zerol：线性建后缀树，行啊。但是 SAM 哪里不好了，非要卡内存（字符集搞得那么大，内存又不给大，明显故意的），一定要体现一下从后缀数组建后缀树的高超技术吗？
 +
 +
== Problem K ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意：求一个菱形六面体的本质不同染色方案数。第 $i$ 种颜色至少用 $c_i$ 次。
 +
 +
题解：一眼 Polya。其实菱形六面体就是正十二面体每个面剖成五个，按照正十二面体考虑就好了。正十二面体有相关资料，比如[http://blog.renren.com/share/192904492/4593049073/0 这个]就讲得还行（虽然看起来还像是标题党）。这个应该对菱形六面体很有启发性。
 +
 +
在三种对称轴，点对称、面对称、棱对称以及不动点上分别进行考虑：
 +
 +
* 点对称：共有 20 种不同的转法（10 种对称轴，每种对称轴上转 2 次），所以在面染色情形下，置换是 3^20（20 个大小为 3 的置换环，这里的 20 不是前面的 20）。
 +
* 面对称：共有 24 种不同的转法（6 种对称轴，考虑五边形），所以在面染色情形下，置换是 5^12。
 +
* 棱对称：共有 15 种不同的转法（30 条棱，可以选出 15 组对称轴），置换是 2^30。
 +
* 不动点：1 种。
 +
 +
这样加起来总共 60 种。同时我们要注意到一个重要的事实：在同一类中，所有置换环的大小都是相等的。这会在解决这个问题中非常有用。
 +
 +
考虑动态规划 $f(i,j)$ 表示选了前 $i$ 中颜色，覆盖了 $j$ 个面的方案数，必须满足 $j$ 是当前情形下置换环大小的倍数（一染就染几个面）。转移的时候，求出最少染的面数（也得是倍数），然后乘上要染哪些面（就是一个二项式系数）。注意由于在模 $60M$ 的意义下计算，计算过程中会出现经典的模数超 int，乘积爆 LL 的问题。
 +
 +
== Problem L ==

Latest revision as of 16:16, 8 August 2018

卡常卡得真刺激。

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 C

Upsolved by ultmaster.

题意：给了一堆基础知识，包括分圆多项式的定义，让你分解 $x^n-1$。

题解：官方题解不知道它在讲什么。

[math]\displaystyle{ \Phi_n(x) = \prod_{1 \leq k \leq n, \gcd(n, k) = 1}{\left(x - {w_n}^k\right)} }[/math]。两边取 log 之后是经典的莫比乌斯。化简的时候要用到著名的结论 [math]\displaystyle{ x^n-1 = \prod_{1 \le k \le n} \left(x - e^{2 \pi i k / n} \right) }[/math]。化出来结果应该是 [math]\displaystyle{ \prod_{d|n} \left(1 - x^{n/d} \right)^{\mu(d)} }[/math]。

Comment: 其实你盯着结果看的话是一眼能看出来的，反演一步就能得到 $\Phi$。

然后 $\mu$ 的值显然只能是 -1 和 1，这个东西就和背包问题很像很像，唯一的问题是 -1 的时候不好办：使用著名的生成函数结论 $\frac{1}{1-x}=1+x+x^2+\cdots$ 转化成无穷背包就好了。官方题解里说这是一个模 $\phi(n)+1$ 的多项式（我感觉在胡说八道）。只是因为预知了超过 $\phi(n)$ 的项最后都不会用到，而且计算过程中永远是从前往后推，高阶项的值在任何时候都不会对低阶项产生影响，所以我们可以安全地忽略他们。（如果是模的话事情反而麻烦了，就是因为看了题解的这句话才陷入了思维的怪圈想了好久。）

至少题解中的复杂度分析是有道理的。该算法复杂度正确基于下面的事实：$\sum_{d|n} \phi(d) = 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 到我优化不动了。可见出题人精确的卡常技术，不得不服。虽然喷了，但这题还是不错的，增加了对点分树的认识。

zerol：可以发现，其实还是求了一次到两个点距离不超过 d 的点的并，虽然这两个点是相邻的。那么也许你想问，既然可以求并，为什么不直接求原问题的答案呢？因为相邻的点在点分树到根的路径最多只有一位之差，如果不相邻可能会差好多，导致虽然不是属于同一棵子树也会有重复计算。

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 I

Problem J

Upsolved by zerol. (-5)

题意：某人从 A 中选了一个子串 B。他会回答你问的是非题，问最优情况下期望几次能够猜出 B。

题解：如果我能知道 A 中恰好出现了 k 次的子串共有 c 个，那么再建一个哈夫曼树就好了。但是数据范围比较大，要求是线性的算法。统计子串用后缀自动机（很可惜，内存不够）或者后缀树（由后缀数组构建，当然这个后缀数组也要线性求）。由于 $\sum k c = \binom{n}{2}$，所以对于入队（伪·优先队列）的分两种情况，如果不超过 n，在数组中合并累计，超过 n 入队列（注意不是优先队列）。数组中的扫一遍就好了，最后队列中有从小到大不超过 n 个元素而且范围是 n+1~2n，这是可以把队列当优先队列用，每次从头上取两个放入尾部（没错，就是单调的），然后就好了而且保证了线性复杂度。

zerol：线性建后缀树，行啊。但是 SAM 哪里不好了，非要卡内存（字符集搞得那么大，内存又不给大，明显故意的），一定要体现一下从后缀数组建后缀树的高超技术吗？

Problem K

Upsolved by ultmaster.

题意：求一个菱形六面体的本质不同染色方案数。第 $i$ 种颜色至少用 $c_i$ 次。

题解：一眼 Polya。其实菱形六面体就是正十二面体每个面剖成五个，按照正十二面体考虑就好了。正十二面体有相关资料，比如这个就讲得还行（虽然看起来还像是标题党）。这个应该对菱形六面体很有启发性。

在三种对称轴，点对称、面对称、棱对称以及不动点上分别进行考虑：

  • 点对称：共有 20 种不同的转法（10 种对称轴，每种对称轴上转 2 次），所以在面染色情形下，置换是 3^20（20 个大小为 3 的置换环，这里的 20 不是前面的 20）。
  • 面对称：共有 24 种不同的转法（6 种对称轴，考虑五边形），所以在面染色情形下，置换是 5^12。
  • 棱对称：共有 15 种不同的转法（30 条棱，可以选出 15 组对称轴），置换是 2^30。
  • 不动点：1 种。

这样加起来总共 60 种。同时我们要注意到一个重要的事实：在同一类中，所有置换环的大小都是相等的。这会在解决这个问题中非常有用。

考虑动态规划 $f(i,j)$ 表示选了前 $i$ 中颜色，覆盖了 $j$ 个面的方案数，必须满足 $j$ 是当前情形下置换环大小的倍数（一染就染几个面）。转移的时候，求出最少染的面数（也得是倍数），然后乘上要染哪些面（就是一个二项式系数）。注意由于在模 $60M$ 的意义下计算，计算过程中会出现经典的模数超 int，乘积爆 LL 的问题。

Problem L

Retrieved from "http://acm.ecnu.edu.cn/wiki/index.php?title=2018_Multi-University,_HDU_Day_5&oldid=683"