Codeforces-170

嘛，wyl8899 问我是不是刷小号……

我才不刷小号呢，我刷的是小小号。

Solution

A

惯例水题。直接用并查集搞搞就可以了。

注意没有一个人会一门语言的情况。我因为这里 WA 了一次。

B

构造。

rng_58 的构造方法：对于 m=3 的情况手算，可以证明若 n>4 则无解。于是这里手算很简单的。

然后考虑两条抛物线： y = x^2 + U 与 -y = x^2 + U ，其中 U 是一个很大的数。如果我们在抛物线上选点，由于抛物线的特殊性质（凹还是凸分不清啊 T_T），可以得到如果两个抛物线上都有点被选，那么这样构出的凸包的大小最多是 4 ，所以如果要选择尽量多的点的话，应该是选择某一条抛物线上的所有点。我们令一条抛物线上点的个数为 m 即可。

C

感觉还蛮简单的。

容易知道每行每列都是独立的，我们可以把这看成是若干个不相关的组合游戏。对于每一行/列，我们只关心没有被覆盖的线段的条数。这个可以用排序+点事件维护，也可以直接用 set 暴力维护。

然后把所有的数 xor 起来就是 SG 了。注意一种特殊情况就是初始时没有出现过的行/列。很显然，我们只关心奇偶。

如何输出方案？一行一列枚举下去，如果通过改变这一行/列可以把 SG 变为 0 则找到一组解。

代码量比较大吧。

D

没看懂题目的说……

E

稍稍一想就发现这是水题。

每个点的出点向所有可能的父亲的入点连边，容量 1 费用为距离。源向每个点的出点连边，容量 1 费用 0 。每个点的入点向汇连边，容量 2 费用 0 。跑一遍费用流，如果最大流是 n - 1 那么有解否则无解。如果有解则最小边权和就是最小费用。

大家都蒯模板啊我还老老实实自己打啊。

situation

本来以为秋锅不做的，结果居然做了。

看完 A 觉得这不是水题吗？于是怒敲代码，写着写着觉得有 bug 于是怒换一种写法。submit 后怒 WA#4 。瞬间想到某特例，加上特判后过 pretest 。

然后 B 。按照惯例，B 应该是水题吧。于是我被惊悚到了，完全不会做啊。YY 了好久想到了用抛物线但就是没想到用两条抛物线。一开始看错题了，以为是要构造一个大小为 n 的点集使得凸包大小恰好是 m 。交了后发现过不了样例才发现看错题了 T_T

瞟了一眼 Dashboard 发现有几个 E 已经出来了，看了一眼 E 觉得不会做。然后看 C 的题目去。看完 C 的题目后发现我会做 E 了 = =|| 于是回去写 E 。1A 。

然后发现 C 不也是水题么。只是处理起来比较麻烦罢了。于是再次怒看错题。然后就没有然后了，1:50 的时候交了个 FST 程序过去。后来调的时候才发现又看错题了 T_T

一看 D 的题目这么长我就直接撤了。目测等我理解完题目 CF 都结束了。

最后 #41 由于是小小号然后还是可以涨的。快追上小号的说～

others

XLk 你真的 AFK 了吗……考完后没人和我聊天了 T_T

scottai1 怒过 ACE 。E 手速还很快的说，于是有 #8 。于是 rating 又超过我了 T_T

wuzhengkai #25 、xiaodao #32 都是 ABE 。我觉得 B 的这个构造很巧妙的说。

watashi 和我一样的，默默 C FST 了。

秋锅 AE #90 。看起来又黄了。

另外我就不吐槽 FredaShi、CatCat、liouzhou_101 三个人的分数都差不多，都是 AB ，提交的时间也差不多，代码也差不多，连 E FST 了都是 T 12 。

ztxz16、sths、edly01、vfleaking 都只过了 A ，而且和我一样，默默 wa 了一次 ……

最后还要吐槽这次 CF 的分数变来变去的，一刷新就发现题目的分数变了。

nonsense

感觉这次 CF 难度很大的说……

然后发现还有人 AK 。

于是感觉 CF#172 也会有好多人 AK 的说。