0%

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)还是很认真的