Difference between revisions of "XIX Open Cup named after E.V. Pankratiev. Grand Prix of America"

From EOJ Wiki
Jump to: navigation, search
(Problem M)
(Problem L)
 
(2 intermediate revisions by the same user not shown)
Line 18: Line 18:
  
 
Solved by Weaver_zhu. 0:14 (+)
 
Solved by Weaver_zhu. 0:14 (+)
 +
 +
温暖的签到
  
 
== Problem E ==
 
== Problem E ==
Line 60: Line 62:
  
 
Solved by Weaver_zhu. 1:38 (+2)
 
Solved by Weaver_zhu. 1:38 (+2)
 +
 +
题意:给 $n$ 个矩形,问是否由两个矩形边界相交
 +
 +
题解:线段树扫描线
  
 
== Problem H ==
 
== Problem H ==
Line 85: Line 91:
 
== Problem L ==
 
== Problem L ==
  
Unsolved.
+
Upsolved by Weaver_zhu.
 +
 
 +
题意:给一个dag任选起点,问走几条路径能把每个点仅走一次。再问哪些点可能成为起点和终点
 +
 
 +
题解:dag上路径覆盖数是拆点后二分图匹配数(心肺停止)。跑完后增广路(当然是走不到终点的增广路)的节点可以是起点和终点
  
 
== Problem M ==
 
== Problem M ==

Latest revision as of 10:09, 12 September 2019

Problem A

Solved by Kilo. 0:59 (+2)

题意:给出一个凸多边形,随机选取其中 $k$ 个点,问其构成的多边形的面积期望是多少。

题解:对于每条有向线段,判断其出现在多边形中的概率,这样就能算出其左边的部分对被删去部分的期望的贡献。统计被删去部分的期望,用面积减去就是答案。

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Solved by Weaver_zhu. 0:14 (+)

温暖的签到

Problem E

Solved by Xiejiadong. 3:36 (+)

题意:在矩阵中选择任意行任意列,求有多少方案,使得被选中的元素按照原顺序组成的矩阵每行每列都是单调的。

题解:$2^m$ 枚举列取或者不取,考虑按照行 dp 。

对于单调,可以把递增的看成 $1$ ,递减看成 $0$ 用来状压。

预处理两两行之间没有列的递增递减关系。

对于行的 dp 只考虑 $\ge $ 两行的情况,那么行的顺序已经由前两行固定了,只需要直接按照情况 dp 转移。

时间复杂度 $O(n^2\cdot 2^m)$

Problem F

Solved by Kilo_5723. 4:44 (+1)

题意:给定一棵树,每个节点的权值是 $[0,b_i]$ 中的随机实数。求这棵树生成一个小顶堆的概率。

题解:另 $f_u(x)$ 代表节点 $u$ 在取 $x$ 时生成小顶堆的概率,我们发现,$b_i$ 会把 $x$ 的值域分成 $n$ 段,在每一段里 $f_u(x)$ 都是幂函数。

因此,对每一个节点 $u$ 按 dfs 序求出 $f_u(x)$。另 $b_i$ 的最大值为 $b_{max}$,对于一个节点,求出其所有子节点的 $f_v(x)$ 之后,$f_u(x)=F_u(x) \cdot \prod_{v(u \;{\rm is \;the\; parent\; of}\;v)}\int_{y=x}^{b_{max}}f_v(y){\rm d}y$,其中

\begin{equation} F_u(x)= \begin{cases} \frac{1}{b_u}& x\le b_u\\ 0& x>b_u \end{cases} \end{equation}

求出 $f_{root}(x)$ 之后,答案就是 $\int_{x=0}^{b_{max}}f_{root}(x){\rm d}x$。

需要用 FFT 求多项式模 $10^9+7$ 下的乘积。

Problem G

Solved by Weaver_zhu. 1:38 (+2)

题意:给 $n$ 个矩形,问是否由两个矩形边界相交

题解:线段树扫描线

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Xiejiadong. 0:21 (+)

题意:求 $s$ 有多少子串的子序列包含字符串 $t$ 。

题解:预处理, $s$ 中每一个位置之后第一个出现的每一个字母的位置,包含 $t$ 的子序列,从每一个位置对应地向后跳即可。

于是枚举 $s$ 的每一个开始位置包含 $t$ 的最前的位置吗,显然从这一位向后都可以作为结束位置,直接统计答案就可以了。

Problem K

Unsolved.

Problem L

Upsolved by Weaver_zhu.

题意:给一个dag任选起点,问走几条路径能把每个点仅走一次。再问哪些点可能成为起点和终点

题解:dag上路径覆盖数是拆点后二分图匹配数(心肺停止)。跑完后增广路(当然是走不到终点的增广路)的节点可以是起点和终点

Problem M

Solved by Kilo_5723. 1:46 (+1)

题意:有一个集合 $\{a_n\}$,定义 $p_i$ 是 $\{a_n\}$ 中与 $i$ 的异或值最小的元素的下标。给出 $p_0,p_1,\dots,p_{2^m-1}$,求有多少合法的 $\{a_n\}$ 集合。保证 $1$ ~ $n$ 都在 $p_i$ 中出现过。

题解:令对于 $p_l,p_{l+1},...,p_r$ 的答案为 $ans(l,r)$,令 $m=\lfloor \frac{l+r}{2} \rfloor+1$,逐二进制位将答案分成两种情况:

第一种:$\{a_n\}$ 中所有数的当前位都相等,此时肯定满足 $p_l,p_l+1,\dots,p_{m-1}=p_{m},p_{m+1},\dots,p_r$,且 $ans(p,l,r)=2 \cdot ans(p,l,m-1)$ (当前位是 $1$ 或 $0$ 都合法)。

第二种:$\{a_n\}$ 中当前位 $0$ 和 $1$ 都有:此时,对于 $p_l,p_l+1,\dots,p_{m-1}$,肯定选当前位为 $0$ 的 $a_i$,而 $p_{m},p_{m+1},\dots,p_r$ 会选择当前位为 $1$ 的 $a_i$。因此在前半段出现过的数不能在后半段也出现,如果不满足这个条件 $ans(p,l,r)=0$,否则 $ans(p,l,r)=ans(p,l,m-1)\cdot ans(p,m,r)$。