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

From EOJ Wiki
Jump to: navigation, search

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)

待补。