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)

Problem G

Solved by Weaver_zhu. 1:38 (+2)

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Xiejiadong. 0:21 (+)

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

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

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

Problem K

Unsolved.

Problem L

Unsolved.

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$ 中出现过。

题解：逐二进制位分两种情况：

第一种：$\{a_n\}$ 中所有数的第一位都相等，此时 $a_0,a_1,\dots,a_{2^{m-1}}=a_{2^{m-1}},a_{2^{m-1}+1},\dots,a_{2^{m}}-1$。