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

From EOJ Wiki
Jump to navigation Jump to search
 
(6 intermediate revisions by 3 users not shown)
Line 15: Line 15:
 
题解:(跟官方题解完全不一样)首先枚举周期 $p$,我们要对 ABC 分别求模 $p$ 下最小的位置和最大的位置。朴素暴力会超时。考虑使用 bitset 优化(去年多校套路),按照 2 的幂,只需要 log 次合并即可。但问题是需要查最低位(bitset 有)和最高位(bitset 霉有)。于是需要自己实现一个 bitset。发生了一系列错误,勉强 AC。
 
题解:(跟官方题解完全不一样)首先枚举周期 $p$,我们要对 ABC 分别求模 $p$ 下最小的位置和最大的位置。朴素暴力会超时。考虑使用 bitset 优化(去年多校套路),按照 2 的幂,只需要 log 次合并即可。但问题是需要查最低位(bitset 有)和最高位(bitset 霉有)。于是需要自己实现一个 bitset。发生了一系列错误,勉强 AC。
  
官方题解的二分,越看越对。
+
另解:把 A,B,C 存在三个 vector 里,然后二分搜索即可。代码短一倍,而且非常好写。
  
 
左移 64 位会出现未定义行为,一定要小心![https://stackoverflow.com/questions/44044170/what-values-are-allowed-for-the-shift-count-operation Reference]
 
左移 64 位会出现未定义行为,一定要小心![https://stackoverflow.com/questions/44044170/what-values-are-allowed-for-the-shift-count-operation Reference]
  
 
== Problem C ==
 
== Problem C ==
 +
 +
Upsolved by zerol.
 +
 +
题意:支持以下操作
 +
 +
123 操作都是往一个集合中放入一个时间戳为 t 的对栈的操作
 +
 +
1. push v
 +
 +
2. delete v (删除最靠近栈顶的 v)
 +
 +
3. pop (不超过 5 次)
 +
 +
4. 对于给定的 t,把所有时间戳不超过 t 的操作按时间戳对一个空栈顺序执行,回答顶部元素。
 +
 +
v 不超过 5,操作保证合法,时间戳各不相同。
 +
 +
题解:对于每个 v 单独维护栈,询问栈顶就比较一下所有栈的栈顶的时间戳。pop 操作就相当于把询问的栈顶元素删掉。所以询问时依次考虑不超过 t 的 pop,每次删掉栈顶元素,最后回答栈顶元素,然后回滚这些删除操作。对于每个 v,开一棵线段树,维护某个时间点栈内的元素个数。如果询问某个时刻 t 前操作的栈顶元素的时间戳,设该时刻的栈内元素个数是 x,那么答案就是不超过 t 的尽可能大的栈内元素个数恰好是 x - 1 的时间戳 +1。为了求这个东西,首先将 [1,t] 区间在线段树上分解成不超过 log 个区间,然后从右往左考虑,如果这个区间内的最小值不超过 x - 1,那么一定能在这个区间内找到答案,所以多维护一个最小值就好了。
  
 
== Problem D ==
 
== Problem D ==
Line 27: Line 45:
 
题意:$n$ 辆公交车,均匀概率地在一个时间点前到,如果 $T_i$ 还没到,就走路,公交车时间 $a$ 保证小于走路时间 $b$,求期望到家时间。  
 
题意:$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$ 段,正确积分即可。
+
题解:两个部分,设 T 为最后等待的时间,最后走路的概率 $p = \prod_{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 ==
 
== Problem E ==
Line 38: Line 56:
  
 
== Problem F ==
 
== Problem F ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意:求小于 $2^n$ 的所有二进制上恰好有 3 个 1 的数构成的集合,有多少个集合异或和是给定数。
 +
 +
题解:显然我们不关心这个给定的数长什么样,我们只关心,这个数二进制上有几个 1。(也就是说 011 和 101 答案应该是相等的)理解这点非常重要,因为下面的 $f(i,j)$ 就是规定二进制上有 $j$ 个 1,然后假设它具有已知的形态(比方说 011)。
 +
 +
$f(i,j)$ 表示选了 $i$ 个,异或结果,恰好有 $j$ 个 1(选取必须不重复,并且不关心选取的顺序)。站在 $f(i,j)$ 的角度倒推,我们关心上一步是怎么来的。那么 $f(i,j)=f(i-1,j+3) \binom{n-j}{3} + f(i-1,j+1) \binom{n-j}{1} \binom{j}{2} + f(i-1,j-1) \binom{n-j}{2} \binom{j}{1} + f(i-1,j-3) \binom{j}{3}$。当然还需要对此结果进行修正,比如最后两步可能选了同样的东西,要减去 $f(i-2,j) \left( \binom{n}{3}-(i-2) \right)$(减去 $i-2$ 是以前选过的东西,由于 $f(i,j)$ 不关心选取的顺序,所以我们可以把可能重复的选择调换到第 $i-1$ 步再选,这样之前就没有重复的可能性)。最后还需要考虑当前选择顺序带来的额外贡献,除以 $i$。
  
 
== Problem G ==
 
== Problem G ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意:给一个黑白棋盘(左右连通,相当于圆柱形),每次翻转一个格子,或者一列,问有多少黑色连通块和白色连通块。
 +
 +
题解:BZOJ1453 增加了翻转一列和左右连通的设定。基本上原题上稍微改改(加个 5 行左右),就做完了。
 +
 +
首先要注意到连通块数目 = 总个数 - 连成森林需要的边数。
 +
 +
基本思路如下,维护一个线段树,每个叶子节点表示一列,在每个节点上维护一个 $2n$ 的并查集,$1$ 到 $n$ 表示这些列中最左边的一列的连通性状况,$n+1$ 到 $2n$ 表示最右边一列的连通性状况。然后 $n+1$ 到 $2n$ 可以往 $1$ 到 $n$ 的里面连(如果采用有向合并会给后面的处理带来便利)。还要在每个节点上维护两个数(连通块个数,表示答案)。合并的时候,父亲(母亲?)节点的连通块个数是两边的连通块个数加起来,然后对中间那两列进行合并,每一次'''有效的'''合并,都会让相应的颜色的连通块个数减 1。实现合并的时候可以将两边大小为 $2n$ 的并查集连起来组成一个大小为 $4n$ 的并查集,然后进行处理;处理完成后,不超过 $n$ 的部分就是我们想要的;超过 $3n$ 的部分,分两种情况:如果根节点不超过 $n$,则保留;否则要把根节点转移到超过 $3n$ 的中间(很有可能是自己,也有可能不是)。然后把这一部分平移到 $n+1$ 到 $2n$ 即可。
 +
 +
翻转一列的话,暴力翻转就好。左右连通的话,查询的时候,开一个 $2n$ 的并查集用上面的方法合并就可以了。
 +
 +
时间复杂度是 $O(qn \log n \cdot \alpha(n))$ 的。有点卡常,如果开两棵线段树可能会超时。但做了原题之后发现根本不用。
  
 
== Problem H ==
 
== Problem H ==

Latest revision as of 03:01, 19 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。

另解:把 A,B,C 存在三个 vector 里,然后二分搜索即可。代码短一倍,而且非常好写。

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

Problem C

Upsolved by zerol.

题意:支持以下操作

123 操作都是往一个集合中放入一个时间戳为 t 的对栈的操作

1. push v

2. delete v (删除最靠近栈顶的 v)

3. pop (不超过 5 次)

4. 对于给定的 t,把所有时间戳不超过 t 的操作按时间戳对一个空栈顺序执行,回答顶部元素。

v 不超过 5,操作保证合法,时间戳各不相同。

题解:对于每个 v 单独维护栈,询问栈顶就比较一下所有栈的栈顶的时间戳。pop 操作就相当于把询问的栈顶元素删掉。所以询问时依次考虑不超过 t 的 pop,每次删掉栈顶元素,最后回答栈顶元素,然后回滚这些删除操作。对于每个 v,开一棵线段树,维护某个时间点栈内的元素个数。如果询问某个时刻 t 前操作的栈顶元素的时间戳,设该时刻的栈内元素个数是 x,那么答案就是不超过 t 的尽可能大的栈内元素个数恰好是 x - 1 的时间戳 +1。为了求这个东西,首先将 [1,t] 区间在线段树上分解成不超过 log 个区间,然后从右往左考虑,如果这个区间内的最小值不超过 x - 1,那么一定能在这个区间内找到答案,所以多维护一个最小值就好了。

Problem D

Upsolved by kblack. (-2)

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

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

Upsolved by ultmaster.

题意:求小于 $2^n$ 的所有二进制上恰好有 3 个 1 的数构成的集合,有多少个集合异或和是给定数。

题解:显然我们不关心这个给定的数长什么样,我们只关心,这个数二进制上有几个 1。(也就是说 011 和 101 答案应该是相等的)理解这点非常重要,因为下面的 $f(i,j)$ 就是规定二进制上有 $j$ 个 1,然后假设它具有已知的形态(比方说 011)。

$f(i,j)$ 表示选了 $i$ 个,异或结果,恰好有 $j$ 个 1(选取必须不重复,并且不关心选取的顺序)。站在 $f(i,j)$ 的角度倒推,我们关心上一步是怎么来的。那么 $f(i,j)=f(i-1,j+3) \binom{n-j}{3} + f(i-1,j+1) \binom{n-j}{1} \binom{j}{2} + f(i-1,j-1) \binom{n-j}{2} \binom{j}{1} + f(i-1,j-3) \binom{j}{3}$。当然还需要对此结果进行修正,比如最后两步可能选了同样的东西,要减去 $f(i-2,j) \left( \binom{n}{3}-(i-2) \right)$(减去 $i-2$ 是以前选过的东西,由于 $f(i,j)$ 不关心选取的顺序,所以我们可以把可能重复的选择调换到第 $i-1$ 步再选,这样之前就没有重复的可能性)。最后还需要考虑当前选择顺序带来的额外贡献,除以 $i$。

Problem G

Upsolved by ultmaster.

题意:给一个黑白棋盘(左右连通,相当于圆柱形),每次翻转一个格子,或者一列,问有多少黑色连通块和白色连通块。

题解:BZOJ1453 增加了翻转一列和左右连通的设定。基本上原题上稍微改改(加个 5 行左右),就做完了。

首先要注意到连通块数目 = 总个数 - 连成森林需要的边数。

基本思路如下,维护一个线段树,每个叶子节点表示一列,在每个节点上维护一个 $2n$ 的并查集,$1$ 到 $n$ 表示这些列中最左边的一列的连通性状况,$n+1$ 到 $2n$ 表示最右边一列的连通性状况。然后 $n+1$ 到 $2n$ 可以往 $1$ 到 $n$ 的里面连(如果采用有向合并会给后面的处理带来便利)。还要在每个节点上维护两个数(连通块个数,表示答案)。合并的时候,父亲(母亲?)节点的连通块个数是两边的连通块个数加起来,然后对中间那两列进行合并,每一次有效的合并,都会让相应的颜色的连通块个数减 1。实现合并的时候可以将两边大小为 $2n$ 的并查集连起来组成一个大小为 $4n$ 的并查集,然后进行处理;处理完成后,不超过 $n$ 的部分就是我们想要的;超过 $3n$ 的部分,分两种情况:如果根节点不超过 $n$,则保留;否则要把根节点转移到超过 $3n$ 的中间(很有可能是自己,也有可能不是)。然后把这一部分平移到 $n+1$ 到 $2n$ 即可。

翻转一列的话,暴力翻转就好。左右连通的话,查询的时候,开一个 $2n$ 的并查集用上面的方法合并就可以了。

时间复杂度是 $O(qn \log n \cdot \alpha(n))$ 的。有点卡常,如果开两棵线段树可能会超时。但做了原题之后发现根本不用。

Problem H

Solved by ultmaster. 01:41 (+)

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

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

Problem I

Solved by zerol. 01:26 (+1)

题意:给一棵树,每个点上都有一个标记,表示向上跳几步。要求支持:1. 修改标记的值。2.询问从 u 开始连续跳,直到跳出树外需要的步数。

题解:每个点向上跳若干步跳到的位置可以用倍增或树剖查询。如果每个点向能一次跳到的点连边,那么这就是一棵树(还需要加一个点表示树外)。那么问题就转化成了换父亲,询问链上的距离。这部分用 LCT 维护,因为要询问距离需要维护一个 size。

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