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