XIX Open Cup named after E.V. Pankratiev. Grand Prix of America

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)$。