Grand Prix of Gomel (ITMO Day 5)

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)$。