Goodbye 2018 A~F 题解

比赛链接：https://codeforc.es/contest/1091。

A

黄色的最多有 /(/min(y,b-1,r-2)/) 个，然后直接输出答案。

代码：https://pastebin.ubuntu.com/p/dqJnf89gdn/。

B

其实答案就是所有向量相加后横纵坐标分别除以 /(n/)。

注意开 long long。

代码：https://pastebin.ubuntu.com/p/SpJbD5X8Jj/。

C

枚举因数，然后就是一个等差数列求和。

将所有结果存下来后排序去重输出即可。

代码：https://pastebin.ubuntu.com/p/H7ZYXBDyN6/。

D

首先，每一个排列单独拿出来肯定可行，这部分答案为 /(n!/)。

然后考虑对于一个排列，它的后 /(i/) 位与下一个排列的前 /(n-i/) 位构成一个排列的条件。

不难发现其实就是后 /(i/) 位不是递减的。

所以我们枚举 /(i/)，在后 /(i/) 位中选若干个数出来重排使得它们不是递减，对于前面的数可以任意重排，那么答案也就是

/[/sum/limits_{i=2}^{n-1}/binom{n}{i}(i!-1)(n-i)!
/]

代码：https://pastebin.ubuntu.com/p/tF9cBzvXhk/。

E

考虑对于一个序列 /(/{d_i/}/)，它是一个简单图的合法度数序列的条件。

首先由握手定理得，/(/sum d_i/) 肯定要是偶数。

有一个 /(/text{Havel-Hakimi}/) 算法，它指出这个问题可以贪心构造。

即将所有点的度数递减排序，然后每次把度数最大的点（称为 /(1/) 号点）拿出来，向其他度数次大的 /(d_1/) 个点连边，那么序列就会从 /(/{d_1,d_2,/dots,d_n/}/) 变成 /(/{d_2-1,d_3-1,/dots,d_{d_1+1}-1,d_{d_1+2},/dots,d_n/}/)。最后会变成两点一边。

还有一个 /(/text{Erdős–Gallai}/) 定理。也是将序列递减排序，那么它可简单图化当且仅当：

/[/forall 1/le i/le n,/sum/limits_{j=1}^i d_j/le i(i-1)+/sum/limits_{j=i+1}^n/min(i,d_j)
/]

其实应该还算好理解，右边是前 /(i/) 个点的边数上界，即完全图 + 后面的点和它的连边。

有向图也有一个类似的：

令 /(n/) 个点按出度降序排列，出度与入度分别为 /(/{a/},/{b/}/)，/(n/) 个点能形成有向图当且仅当：

/[/forall 1/le k/le n,/sum/limits_{i=1}^k a_i/le /sum/limits_{i=1}^k /min(b_i,k-1)+/sum/limits_{i=k+1}^n /min(b_i,k)
/]

参考：https://www.cnblogs.com/Grice/p/12894688.html。

在本题中，还有一个性质：因为 /(d_{n+1}/) 的奇偶性已经确定，所以满足条件的 /(d_{n+1}/) 一定是一段区间里奇偶性相同的若干个数。

那么我们就可以二分出上下界。具体的，在 check 函数里使用插入排序，然后依次校验那个式子，然后我们可以得出当前的 /(mid/) 要调大还是调小。

代码：https://pastebin.ubuntu.com/p/PBwzbbGsZv/。

F

首先，我们在草上走水里游一定比积蓄能量然后在草上和水上飞更优。

可以直接模拟这个过程。然而可能会遇到飞的时候能量不够的情况，这时我们就可以在之前草上或水里增加能量。如果有水就优先在水里游，因为消耗的时间更少。

最后可能会有能量多出来的情况，这个时候就需要在草上或水上飞来减少时间。

每次减少时间都会消耗 /(2/) 的能量。因为我们不但没有得到能量，还减少了能量。

最优策略肯定是优先在草上飞。

记录当前走过的草的长度 /(gr/)，那么能够在草上飞的时间就是 /(/min(gr,/frac{stamina}{2})/)，其中 /(stamina/) 为能量值。

需要注意 /(gr/) 要时刻与 /(stamina/) 取 /(/min/)，因为后面可能会出现要飞的时候能量不够的情况。

在水上飞的时间就是 /(stamina-/min(gr,/frac{stamina}{2})/) 了。

为了避免浮点误差，我们可以将 /(gr/) 和 /(stamina/) 全部 /(/times 2/)。

代码：https://pastebin.ubuntu.com/p/hb9CtJhsBF/。