2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1

Problem A

Upsolved by zerol.

类 FWT。

题解写在这里了

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Solved by zerol. 01:27 (+1)

题意：已知一个 k 项的线性递推式，要求一组 $c_i$，使得 $f_n = \sum_{i=1}^k c_i f_{n - b_i}$ 与之等效，其中 $b_i$ 已知。

题解：令 D 是一个很大的数，用 $f_{n-D}, f_{n-D-1}, \dots, f_{n-D-k+1}$ 的线性组合来表示 $f_n$，对于给定的递推式，那么系数已知，对于需要填充参数的递推式，每一个系数都是 $c_i$ 的线性组合，那么得到了一个线性方程组，由于数据的随机性，那么可以认为这个方程是满秩的，可以方便得得到解。其中求线性组合的系数需要用到多项式快速幂（是线性递推求某一项的加速算法中的一部分，复杂度是 $O(\log n \cdot k^2)$），解方程就是最方便的那种高斯消元。

zerol: 我的自主研发板子有一个漏洞，就是不支持一项的递推，会 RE（已经坑了我两次了）。这次因此以十几秒的差距错失了一血。

Problem E

Solved by zerol. 00:14 (+)

伪装成博弈的温暖签到。

Problem F

Upsolved by zerol & ultmaster. (-3)

题意：无向图，有一些边是树边，另外一些边不是。定义一条路径的瓶颈为路径上的权值的最小值。一个点是罗马的条件是，它不会抄近道，也就是说，它到所有点的只经过树边的路径的瓶颈都比有经过非树边的路径的瓶颈大。求所有可能的罗马点。

题意：一个观察就是：把边从大往小加进来，如果加进来的是树边，那么如果两点间已经连通，它连接的两块点就都炸了；如果加进来的是非树边，那么如果两点间还未连通，它连接的两块点也炸了。但是有边权相同，需要 group by w, type 一批一批的加进来。把炸了的边记下来，最后从后往前扫染色一遍就好了。

Problem G

Unsolved.

Problem H

Solved by ultmaster. 01:45 (+1)

题意：无穷轮的游戏，先手看到屏幕上出现一个 $1$ 到 $n$ 之间的数字，可以自己拿然后轮到对方，也可以逼对方选然后还是轮到自己。求先手最后赢多少。

题解：$ans = \frac{1}{n} \sum_{i=1}^n |ans-i|$。二分答案的范围，然后绝对值打开，解方程。

U：然而不会解方程。

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Solved by kblack. 00:18 (+)

温暖的签到。