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

From EOJ Wiki
Jump to navigation Jump to search
 
(10 intermediate revisions by 2 users not shown)
Line 2: Line 2:
  
 
kblack: 按去年青岛,35 个金,三题手速金,传奇再现。
 
kblack: 按去年青岛,35 个金,三题手速金,传奇再现。
 +
 +
zerol:零贡献。被 TLE 和 MLE 搞自闭了。
  
 
== Problem A ==
 
== Problem A ==
Line 22: Line 24:
  
 
== Problem C ==
 
== 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 ==
 
== Problem D ==
Line 31: Line 47:
 
题解:设 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 的直接儿子的子树中的情况时深度要按新的二合一深度计算。
 
题解:设 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:又是 MLE 又是 TLE。MLE 逼我把倍增 lca 换成了树链剖分,还把指针换成了数组下标。在开两倍点的情况下,两个 log 本地 16s,一个 log 本地 11s,杭电就是 T,T 到我优化不动了。可见出题人精确的卡常技术,不得不服。虽然喷了,但这题还是不错的,增加了对点分树的认识。
 +
 
 +
zerol:可以发现,其实还是求了一次到两个点距离不超过 d 的点的并,虽然这两个点是相邻的。那么也许你想问,既然可以求并,为什么不直接求原问题的答案呢?因为相邻的点在点分树到根的路径最多只有一位之差,如果不相邻可能会差好多,导致虽然不是属于同一棵子树也会有重复计算。
  
 
== Problem E ==
 
== Problem E ==
Line 82: Line 100:
 
== Problem J ==
 
== Problem J ==
  
Unsolved. (-5)
+
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 ==
 
== 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 ==
 
== 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