Grand Prix of Khamovniki, MosCode Fest Online Selection (ITMO Day 6)

Problem A

Solved by ultmaster. 01:27 (+)

题意：非常复杂。大致就是说有一堆人按顺序选大技能小技能，大技能只能选一个。最优化队伍技能和。求最优策略下的结果。

题解：状压一下暴搜搜就好了。没大写过博弈类状压的 ultmaster 现在也学会了。

Problem B

Unsolved.

题意：一棵树，每条边的期望长度服从 $U(0,1)$，求树的期望直径。

Problem C

Solved by kblack. 00:50 (+)

题意：给出一张图，要求找到一个节点，其他所有节点都直接与其相连，或排他性的通过另一个节点，以距离 2 与这个节点相连，并输出方案。

题解：枚举这个节点，剩下的点建立二分图。左边是距离为 2 的节点，右边是距离为 1 的节点，如果距离为 2 的全部可以匹配，则可以直接构造方案。

Problem D

Unsolved.

Problem E

Unsolved.

题意：$Oneness(x)$ 是指，在 1,11,111,1111,... 这样的数中有多少个能整除 $x$。求 $\sum_{i=1}^n Oneness(i)$。$n$ 是随机生成的，不超过 $250~000$ 位。

Problem F

Upsolved by ultmaster.

题意：给定一个偶数长的字符串，规定 $\mathrm{shuffle}(s)=s_1s_3\ldots s_{n-1}s_2s_4\ldots s_n$。求需要多少次 shuffle 操作才能把 $a$ 变成 $b$。

题解：shuffle 是一种置换操作，能够求出置换环。在置换环内用 KMP 求出最小达到的步数，并求出置换的周期。用 CRT 求得答案。

Problem G

Upsolved by ultmaster. 04:58 (-41)

题意：给定一些点，问这些点连成的直线能否表示成 $f(x)=\sum_{i=1}^m \lambda_i |x-a_i|$。

题解：简单列出方程就可以求出所有 $\lambda$，由于方程比未知数数量多一个，必须代入一个方程验证是否成立。遗憾的是，此题精度上无法卡过，GG。

正确的做法是 $\bmod P$ 进行验证，也可以大力化简方程 $O(1)$ 验证。ultmaster 立了个大 flag。然后使用各种语言，交了 40 多次。。。对此题的失败负有重大责任。

Problem H

Solved by kblack. 02:14 (+2)

题意：要求构造一个长度为 n，每个数字不超过 m，最长上升子序列是长为 k，序列中某些位置固定的正整数序列。

题解：只需将目标子序列放在最右侧，每个未知位置填充左侧的值（最左侧则填充 1）之后在序列最左侧从大到小添加数字，注意数量保证不会导致最长上升子序列的改变即可。

Problem I

Upsolved by ultmaster. 02:15 (-2)

题意：交互题。给出 $n$ 个栈，每个栈有 $k$ 个元素。每次你选择一个 $x$，然后机器会选择一个符号 $\ge$ 或 $\le$，表示移除栈顶上 $\ge x$ 或 $\le x$ 的元素，然后会返回栈顶的所有元素。要求在若干次操作内全部移完。

题解：一种明显的错误解法是每次选择中位数，这样选择的错误之处在于可能有一些栈永远得不到移除，我们有的时候需要迫使机器将那些高度大的栈进行移除（选择相等的元素）。由此我们需要做一些小修改，将中位数改成加权中位数，权重为 $2^h$（$h$ 为栈的高度）。

Problem J

Unsolved.

Problem K

Solved by zerol. 01:37 (+2)

待补。