0%

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 的说。