Codeforces-185

一来就发现 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

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

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

其中必有隐情。

疑心重重， \(\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）还是很认真的