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

Problem A

Unsolved.

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

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