Grand Prix of Gomel (ITMO Day 5)

From EOJ Wiki
Jump to: navigation, search

Problem A

Solved by ultmaster. 00:07 (+)

签到。

Problem B

Solved by kblack. 00:57 (+)

题意:将 $n$ 分成若干个数,使得每个数的出现的次数二进制上 1 的个数之和最大。

题解:不会。

Problem C

Upsolved by ultmaster.

题意:构造一个 $n$ 边形,使得恰好有 $k$ 条内对角线。

题解:先构造一个内对角线最少的 $n$ 边形,然后逐步增多对角线。

Problem D

Upsovled by ultmaster.

题意:有 $n$ 个猴子,$i<j$ 可以保证有 $p$ 的概率能打赢。求选出 $k$ 个使得这 $k$ 个猴子能全部战胜 $n-k$ 个猴子的概率。

题解:

若 $p=\frac{1}{2}, f(k)={n \choose k} 2^{k(k-n)}$;

若 $p\ne \frac{1}{2}$,$f(k+1)=f(k) \frac{(1-p)^{n-k}-p^{n-k}}{(1-p)^{k+1}-p^{k+1}}$.

Problem E

Unsolved.

题意:电影院中有些座位已经被占了,求有多少种方案可以买到一排中连续的若干个座位。

Problem F

Solved by zerol. 02:49 (+)

题意:每个选民有一个有序的候选名单。每一轮投票时,选民会选出候选名单中票数最多的那位,如果有两人并列,则选择名单上靠前的。投票结果不变时不再投票。构造一份名单集,使得投票至少要进行 $p$ 轮。

题解:使得每一轮恰好有一个人倒戈给 1。

Problem G

Solved by kblack. 04:55 (+8)

题意:问有多少个不同的等差数列 $\{a_i\}$ 使得 $l_i \le a_i \le r_i$。

题解:考虑枚举 $d$,求可能的 $a_0$ :由 $l_i \le a_0 + d \cdot i \le r_i$,可以得到 $a_0$ 有关 $d$ 的两个函数:$a_0=l_i-id,a_0=r_i-id$。总共可以得到 $2n$ 的函数,这 $2n$ 个函数可以交出一块区域。对于每一个 $d$,在可行域内都有 $a_0$ 的一个上界和一个下界。

kblack 绝杀,完成唯一一个 Last Hour。

Problem H

Unsolved.

题意:在 $1$ 到 $n$ 的数轴上走路,要走成哈密尔顿回路。有一定条件可以飞(互质的情况下)。问最少要飞几次。

题解:(口胡)据说最多只要 3 次。3 次的时候 Randomly check 一下。

Problem I

Unsolved.

Problem J

Upsolved by ultmaster.

Problem K

Solved by zerol. 03:20 (+1)

题意:求有多少个非空集合满足 $gcd=1$ 且 $lcm=m$。

题解:$m=p_1^{k_1}p_2^{k_2} \cdots p_n^{k_n}$。这个集合中一定满足对于每一个质因子都有一个数质因子幂为 $0$,都有一个数质因子幂为 $k_i$。也就是说对于每一个质因子而言都存在两个规定要存在的东西。运用容斥原理。答案等于:全体,减去不存在一个的数量,加上不存在两个的数量,云云。问题在于 $n=15$,$2n=30$,直接这样做会超时。我们注意到对于每个质因子有两部分的答案是对称的。由此可以优化到 $O(3^n)$。