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

From EOJ Wiki
Jump to navigation Jump to search
Line 64: Line 64:
  
 
Solved by zerol. 02:04 (+)
 
Solved by zerol. 02:04 (+)
 +
 +
题意:有 k 维属性,对于每个怪物,如果每一维属性都大于等于它的话,就可以击败他,然后每一维属性都增长一个非负整数。求最后能击杀的怪的数量和最后属性值。
 +
 +
题解:怪物肯定能杀就杀。对于所有怪物,按照每一维从小到大排序,用 k 个指针维护当前这一维属性能被击败的怪并标记,一旦一个怪物被标记了 k 次就挂了。

Revision as of 14:39, 13 August 2018

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。

官方题解的二分,越看越对。

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

Problem C

Problem D

Upsolved by kblack. (-2)

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

题解:两个部分,设 T 为最后等待的时间,最后走路的概率 $p = \sum_{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

Problem G

Problem H

Solved by ultmaster. 01:41 (+)

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

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

Problem I

Solved by zerol. 01:26 (+1)

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 次就挂了。