一来就发现 roosaphu #1 。

然后 cp12321 #2 。

然后 kAc #5 。

其中必有引擎。我就呵呵不说话。

（这场 CF 真心是给国人做的）

（我不知道我对 unrated 是该高兴还是该悲伤）

Solution

B

原题可以抽象出这么个模型：给定 $m$ 个数，要求分成 $p$ 组，最后每个元素对答案的贡献为它所在组的最大值，求答案的最小值。

排序是显然的。然后序列上 dp ： $f_{i, j}$ 表示前 $i$ 个数分成 $j$ 组，最小的总贡献是多少。转移考虑转入，枚举第 $j$ 组的元素个数。

$$f_{i, j} = \min_{k < i} (f_{k, j - 1} + (i - k) x_i) = i x_i + \min_{k < i} (f_{k, j - 1} - k x_i)$$

然后就可以斜率优化了。考虑两个决策 $p < q < i$ ， $q$ 比 $p$ 优的充要条件是 $f_{p, j - 1} - p x_i > f_{q, j - 1} - q x_i$ 也就是

$$x*i > \frac{f*{q, j - 1} - f\_{p, j - 1}}{q - p}.$$

我相信只要你看了 杨哲 《凸完全单调性的一个加强与应用》，你就一定会做这个题。

C

我相信只要你看了 周奕超 《墨墨的等式》 出题报告，你就一定会做这个题。

一眼题不多说。

D

问题主要就出在那个啥三次方上吧。

你有没有感到很奇怪，为啥会给一个奇怪的数 9554272，还特意说明这是个素数？

其中必有隐情。

疑心重重， $\phi(95542721) = 95542720$ ，这个数与 3 是互质的。

于是我们试着在 $\mod{95542720}$ 的意义下求 3 的幂。

于是乎，你会发现 $3^{48} \equiv 1 \mod{95542720}$ 。

剩下的就不用我多说了。用线段树维护 0 到 47 次立方后的结果。

E

我相信只要你做了 Topcoder SRM 558 Div1 1000pts SurroudingBoard ，或者听懂了 曹钦翔 《线性规划与网络流》 ，你就一定会做这个题。

首先那个啥 friend 是用来搞笑的。

每个变量可以取 0 或 1 ，有些取 0 需要代价，有些取 1 需要代价。有种网络流的既视感……

剩下的就是那个特殊的获利的方法：当若干个变量全 0 或全 1 的时候，可以获得一定利润。

如果你突然有了 IDEA ，可以直接构出图：先把利润全部加入答案，然后对于每种获利方式建立一个节点。考虑啥时候需要这利润从答案里扣除。不妨设此时的限制为某些变量全 1 就得到利润吧，那么必定是这些变量中的一些为 0 那么就得扣除利润。某些变量为 0 的话，网络流中的表示为与 T 连通，我们直接把 S 连向利润这个点，容量为利润，再把利润这个点连向与其相关的那些变量，容量无穷大。这样的话一旦有个变量为 0 （图上对应的就是与 T 连通），那么利润这个点必定与 T 连通（无穷大的边你割不去），所以必定要割掉 S 与利润这个点的连边，相当于减去了利润。这就是个最小割模型。

当然你要是牛逼，直接上 cqx 的线性规划也是可以的。我试了一下，发现 SurroudingGame 和这个题都可以用线性规划建模的方法通杀，无比炫酷。

nonsense

节操掉尽，请勿再念。

@xiaodao 关于 #183 D 的 solution …… 我只能说 what the heck 当初觉得很明显的一步我居然不会证 →_→ 于是剩下的就坑了。

首先要证明数的大小一定是 $\frac{1}{n+1}$ ，然后就好证明了。（这一步怎么证明……我只能说 wiki 上有一句原话） 对于 $kx = \frac{k}{n+1} = b^p x - q$ ，我们有 $k = b^p - q(n+1)$ ，在 $\mod{n+1}$ 意义下有 $k=b^p \mod{n+1}$ 。由于对于每个 $k$ 都存在这么一个 $p$ ，所以容易知道 $n+1$ 一定为质数，且 $b$ 是 $n+1$ 的一个原根。

这次 CF 被拉过去当 Tester ，就写了 BCDE 的没写 A ，结果 A 的 checker 就挂了，真是不能更逗。不得不说他们几个（@lyd, @wqs, @zgx）还是很认真的