首先向牛客同步赛的各位致歉，线下赛的网络环境出的问题导致我校后台人员工作过饱和失能了，一不小心把开始时间设置错了。很抱歉给各位造成了一定的困扰。

本场题解PDF版点击这里获取。

A

题目要求找到最小时间 $t$ ，考虑二分。

对于二分出的时间 $mid$ ，对于所有准备好的调料，可以预处理出后缀和 $suf$ 。从前往后遍历所有披萨，当前披萨 $i$ 的灵力值可以 $O(1)$ 计算为 $c_i \times (suf_{i 1} 1)$ 。如果存在一个披萨灵力值 $\geq k$ ，那么返回 $true$ ；反之返回 $false$ 。

B

本题是用于防 AK 的大模拟。题目背景取自三国杀。其中的题目数据也有改自游戏某关（BV1uN411g7RT P143）。

标准程序使用了 BFS 对每一步可能到达的移动结果进行广搜并记录状态，但由于限制了步数，也可以采用 DFS 剪枝的方式进行深搜。

标准程序所计算出来的最短解法如下（不包含样例，按 case 顺序输出）。

9
dwwadsdwa
20
aawdsdsdsaasawaawdds
25
wadsdwwasadwawssdswdwdssa
30
sawawawsdwasdasawdwawdsdwdsasd

C

对于本题，可行的解法是线性时间复杂度的动态规划。

设 $f_{i,0/1}$ 表示第 $i$ 个单元格涂上红色/蓝色能获得的最大分数，我们可以得到以下方程：

\begin{cases} f_{i,0} = a_i max(f_{i - 1,0} c_{i-1} c_i,f_{i-1,1}) \\ f_{i,1} = b_i max(f_{i - 1,1} c_{i-1} c_i,f_{i-1,0}) \end{cases}

最终的答案为 $max(f_{n,0},f_{n,1})$ 。

D

暴力枚举给定排列，使用一个数组记录当前数字的使用情况。从头开始执行遍历流程，如果当前数字没有被使用，则它在遍历过程中第一次出现并且属于当前的循环节，将其标记后记录当前循环节的长度增加。当遍历到被使用的数字时，证明该环已经全部遍历完成，计算总长度以后与最大值和最小值分别比较。再寻找下一个没有被使用的数字开始新的枚举流程，以此类推。

E

这是一个经典的数学题，现在我们拿 $100$ 个囚徒 $100$ 个盒子来举例，随机排列的 $100$ 个盒子，包含长度为 $100$ 的循环概率是多少？显然，答案是 $\frac{1}{100}$ 。

这是一个普遍的结果，长度为 $99$ 的概率是 $\frac{1}{99}$ ，长度为 $98$ 的概率是 $\frac{1}{98}$ ，因此推广到长度超过 $50$ 循环的概率就是 $\frac{1}{100} \frac{1}{99} ... \frac{1}{52} \frac{1}{51}$ ，这个数字大概是 $0.69$ ，即囚徒们失败的概率，再拿 $1$ 减去这个数即囚徒们成功的概率。以此说明推广到 $N$ 个囚徒和 $N$ 个盒子，发现这就是一个简单的数学公式，答案为 $1-[\frac{1}{N} \frac{1}{N-1} \frac{1}{N-2} ... \frac{1}{\frac{N}{2} 2} \frac{1}{\frac{N}{2} 1}]$ ，复杂度为 $O(\frac{N}{2})$ 。

下面是对于包含长度为 $N$ 的循环出现概率为 $\frac{1}{N}$ 的补充证明：

先举个简单的例子： $3$ 个囚徒 $3$ 个盒子，所有组合是：

$1 \enspace 2 \enspace 3$ ： $3$ 个 $1$ 阶循环。

$1 \enspace 3 \enspace 2$ ： $1$ 个 $1$ 阶循环， $1$ 个 $2$ 阶循环。

$2 \enspace 1 \enspace 3$ ： $1$ 个 $1$ 阶循环， $1$ 个 $2$ 阶循环。

$2 \enspace 3 \enspace 1$ ： $1$ 个 $3$ 阶循环。

$3 \enspace 1 \enspace 2$ ： $1$ 个 $3$ 阶循环。

$3 \enspace 2 \enspace 1$ ： $1$ 个 $1$ 阶循环， $1$ 个 $2$ 阶循环。

设 $P(x) =\text{形成} x \text{阶循环的概率}$ ，有

\begin{cases} P(1) = \frac{4}{6} = \frac{2}{3} \\ P(2) = \frac{3}{6} = \frac{1}{2} \\ P(3) = \frac{2}{6} = \frac{1}{3} \end{cases}

那么 $100$ 个囚徒 $100$ 个盒子呢？

对于 $x \in [51,100]$ 来说，出现一个循环后，剩余循环组合里必然不会出现其它 $len>50$ 的循环了，所以这些循环是互斥的。所以，我们先从100个选 $100-x$ 个进行排列组合，然后剩余的 $x$ 个组成循环。得到计算公式 $P(x)=\binom{100}{x} \cdot (100-x)! \cdot \frac{x!}{x \cdot 100!}=\frac{1}{x}$ 。

以上结论经过推广，到 $n$ 个盒子就有 $P(x)=\binom{n}{x} \cdot (n-x)! \cdot \frac{x!}{x \cdot n!}=\frac{1}{x}$ 。

F

字符串长度并不长，唯一的坑点是因为存在空格，所以需要使用 getline 读入。查询的方式就比较多样，不再赘述。

G

首先对原点集求凸包，将该凸包顶点与其边上的点从原点集中剔除，再进行一次求凸包。将两次求得凸包的面积相减即可得到魔戒的面积。

因为数据保证所有点不会均在同一条直线上，第一次切割必然能够得到一个合法的多边形，但第二次切割时就可能出现没有点或点均在一条直线上的情况，注意对于这些情况的判断。

依据Pick定理，我们可以得知最终求得面积的二倍一定是一个正整数，加之本题的数据范围较大，运算应在整数域中进行，以保证不会出现精度问题。

H

本题数据范围较小，做法较多。其中一种做法是枚举所有选取节点的方案，判断是否联通和连接未选取的节点，记录花费最小的方案。判断联通可以用并查集，判断连接节点可以用 BFS 。

I

根据题意可知，在任意两位大学生 $A \enspace B$ 之间，其中位置相对靠后的大学生必然因靠前的学生产生 $h_{self} \cdot t_{other}$ 的不满度，而靠前的大学生不会对靠后的学生产生不满度。也就是说，任意两位大学生之间必然有一次不满度产出，且不满度产出只和二人之间的顺序有关。因此，我们只要贪心的保证每两个人之间的不满度产出均最小，即可保证总不满度最小。