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$ 中出现过。
题解:令对于 $p_l,p_{l+1},...,p_r$ 的答案为 $ans(l,r)$,令 $m=\lfloor \frac{l+r}{2} \rfloor$,逐二进制位将答案分成两种情况:
第一种:$\{a_n\}$ 中所有数的当前位都相等,此时肯定满足 $p_l,p_l+1,\dots,p_{m}=p_{m+1},p_{m+2},\dots,p_r$,且 $ans(p,l,r)=2 \cdot ans(p,l,m)$ (当前位是 $1$ 或 $0$ 都合法)。
第二种:$\{a_n\}$ 中当前位 $0$ 和 $1$ 都有:此时,对于 $p_l,p_l+1,\dots,p_{m}$,肯定选当前位为 $0$ 的 $a_i$,而 $p_{m+1},p_{m+2},\dots,p_r$ 会选择当前位为 $1$ 的 $a_i$。因此在前半段出现过的数不能在后半段也出现,如果不满足这个条件 $ans(p,l,r)=0$,否则 $ans(p,l,r)=ans(p,l,m)\cdot ans(p,m+1,r)$。