Petrozavodsk Winter Training Camp 2018 ITMO U Contest (ITMO Day 2)

From EOJ Wiki
Jump to: navigation, search

Problem A

Unsolved by Mathematica.

题意:有 $n$ 个柜台,每一个柜台有一个固定的处理时间 $t \sim U(l,r)$,实际需要处理的时间 $t' \sim U(0,t)$。求 $\mathrm{Prob}(t \mathrm{\ is\ minimum}| t' \mathrm{\ is \ minimum})$。

题解:

题解说答案(显然)是:$\displaystyle n \frac{1}{(r-l)^n} \int_{l}^r \text{dt } \frac{1}{t} \int_{0}^t \text{dx } \left( \int_t^r \text{dy } (1- \frac{x}{y} ) \right)^{n-1}$。行吧。

里面两层积分手算一下。行吧。

然后分 $n=2,3,4$ 用 Mathematica 积分下。行吧。

然后就是一个超长的式子。随便搞一搞。就算 AC 了。

只为了贯通 A 题。这么做感觉没什么意义啊?

Problem B

Unsolved.

题意:一颗带边权的无向树,有巡逻路径 $v_1,v_2,\ldots,v_k$。目标是从 $s$ 到 $t$ ,不能在路径上与巡逻相遇。

Problem C

Solved by zerol. Upsolved by ultmaster. 03:59 (+9)

题意:交互题。起始时庄家拥有一块巧克力。游戏共进行奇数轮。玩家是先手,每一轮可以从对方的巧克力中选择一块切 $(\frac{1}{3}, \frac{2}{3})$ 收入囊中。庄家没有策略,随机选择,切 $\frac{2}{3}$ 。求一种策略,使得最终获得的巧克力大于 $0.55$。

题解:第一次取 $\frac{1}{3}$,最后一次将剩下的 $\frac{2}{3}$ 中取出 $\frac{2}{3}$。那么中间只需要获利 $0.1$ 即可。注意到每次取最大的取 $\frac{2}{3}$ 可以获利约 $0.5$。

其实一开始的做法就是对的,ultmaster 写错背了大锅。后来用一种诡异的做法过了。

Problem D

Solved by kblack. 01:49 (+1)

题意:给出 $2^n$ 个人的锦标赛,问排名为 $k$ 的人期望能打的轮数。

题解:$\mathrm{Prob}(\mathrm{Will \ participate \ in \ round} \ i) = \displaystyle\frac{\mathrm{worse} \choose 2^{i-1}-1}{\mathrm{all} \choose 2^{i-1}-1}$ 。求阶乘时取对数以避免浮点数误差。

Problem E

Unsolved.

题意:有 $n$ 个人的锦标赛($n$ 可能为奇数)。每轮都重新分组(可能有人轮空),问有多少种可能性。

Problem F

Upsolved by ultmaster.

题意:求有多少个 $n \times m$ 的 01 矩阵满足:所有 0 都连通,所有 1 都不连通。

题解:首先状压 DP,可以使用类似并查集的方法记录状态,然后通过广搜的方法加边,搜出所有状态所有边。然后跑出 $n \le 2000$ 时的答案。然后猜通项满足一个齐次线性递推,使用 Berlekamp-Messy 算法在 $O(n^2)$ 时间内解出线性递推的系数。然后使用特征多项式优化转移矩阵快速幂,就可以在 $O(k^2 \log m)$ 时间内求到答案。这里 $k \approx 900$。

后两步有模板,难点在状压 DP。

Problem G

Solved by kblack. 01:33 (+2)

题意:有 $n$ 张椅子排成一排,每张椅子都有一个颜色,每种颜色都有 $1/c$ 的概率被裁判选中。一开始要选择一张椅子,使得走到被裁判选中的颜色的椅子的最少步数的期望值最小。

题解:相当于是 $c$ 个函数。所有函数的拐点不会太多。所以从左到右扫描模拟即可。

kblack 看错题,以为是一个圈,居然神奇地过了样例。

Problem H

Upsolved by kblack.

题意:求一个排列 $p$,最小化 $\displaystyle\sum_{i=1}^n \min_{1\le j \le i} a_{p_i} \oplus b_{p_j}$。

题解:枚举排列的前缀,在 $i$ 向 $j$ 之间连边,代价是 $a_j \oplus b_i$。$-1$ 到 $i$ 连单向边,代价为 $a_i \oplus b_i$。以 $-1$ 为根跑最小有根生成树。

Problem I

Upsolved by ultmaster.

题意:给一个字符串,问有多少子串符合给定的模式。模式是:规定字符串的某些位置相等。

题解:在相等的两个关系之间列出一个多项式,然后将原串倒置,做卷积就能得到答案。例如:

模式串是 `1 2 2 3 2 3`,列出多项式 $a_1(x^2-x^3)+a_2(x^3-x^5)+a_3(x^4-x^6)$ ,其中 $a_1,a_2,a_3$ 是随机选取的。原串是 `3 2 2 1 2 1 1`,将其反转得到 `1 1 2 1 2 2 3`,对应的多项式为 $1 x^1+1 x^2 +2 x^3 + 1 x^4 + 2 x^5 + 2 x^6 + 3 x^7$。做卷积后可以发现每一个匹配的位置恰好对应多项式的一项。匹配成功当且仅当该项系数为 $0$。

Problem J

Solved by zerol. 01:50 (+)

题意:跳砖块。每次可以跳砖块上写的数字格,或者上次跳的长度。问 $1$ 到 $n$ 的方案数。

题解:

  • 如果直接 dp,需要为下标为等差数列的 dp 加上一个值,如果差比较小,那么操作次数会很多。
  • 如果公差大于 $\sqrt{n}$ 那么直接操作。
  • 如果小于 $\sqrt{n}$ 那么暂且标记一下,开个数组 add[d]\[k]=v 表示下标模 $d$ 余 $k$ 的数字都加上 $v$。处理到当前下标时枚举公差累加。
  • 复杂度 $O(n\sqrt{n})$
  • 这题还有个问题,如果跳的路线一样,但是同样的数字来自于不同的砖块,那么只算一次。也就是说如果是跳 $d$ 过来的,而当前砖块上面恰好也是 $d$,这部分的值是不往后更新的。(这一点写完过不了样例后才发现。)
  • 由于这个特性,对于所有的公差,如果重复出现的话只有第一次是有效的,那么可以暴力更新,复杂度也是有保证的。

Problem K

Unsolved.

Problem L

Upsolved by ultmaster | zerol.

题意:考试考的知识点是服从 $U(0,1)$ 的一个随机变量。每天可以 cover 一段知识点,不通过当天的考试的话,明天继续。必须要在 $k$ 天内通过。知识点不会忘记。求学习知识量的期望的最小值。用分数 $\frac{P}{Q}$ 表示,分别求 $P \bmod M, Q \bmod M$。

题解:$f(1)=1,f(k+1)=\min_t (t^2+(1-t)f(k))=f(k)-\frac{f^2(k)}{4}$。这一递推关系会使得 $f(k)$ 的周期在 $\sqrt{M}$ 级别。所以先求出 $\frac{P}{Q} \bmod M$,再求出 $Q \bmod M$,最后求出 $P \bmod M$。