2018 Petrozavodsk Winter Camp, Yandex Cup

链接

A. Ability Draft

神必大模拟。

C. Block, Stock and Two Smoking Galaxy Notes

K. Hiding a Tree

H. Hiding a Tree

签到题。

F. Shuffle

考虑一次操作显然是一个置换,所以一定会构成一个环。

对于环等价于环同构,直接 exKMP/Hash 即可。

考虑环长的限制,显然本质不同环长是 $O(\sqrt n)$ 的,对于长度相同的环一起暴力推,复杂度 $O(n\sqrt n)$。

事实上可以证明环长一定是 $\phi(n-1)$ 的约数,所以不同长度的环数就更小了。

G. Piecewise Linearity

条件有两个,一个是最左端与最右端右斜率相反,另一个是不能加常数。

第二个很难判断?其实直接强行构造即可。最后如果构造不出来即无解。

I.  ≤ or ≥

考虑设置权重函数 $f(k)=3^k$,总权重为 $S$,带权二分,可以发现每次相当于选择一个较小一边除以 $3$,这样至少使权重减少 $\frac 13S$。

毛估估一下大概就是 $50$ 左右。