0%

Codeforces-158-div2

今天刷小号的 = = ,然后其余人为了保证充足的睡眠以及有规律的生物钟没参加了。反正我的生物钟已经被完完整整地破坏了,那就大胆的被虐吧~

solution

A

水题,暴力枚举每一位即可。

hack 人的时候发现只要枚举第一位就可以了,其余的全部填 0 。不过反正差不多快啦,5 min。

B

水题,枚举即可。

我居然看到有人判日期直接判 31 。随手一个数据过去就挂了。

还看到有人没判中间的 - ,本来想 hack 的,但是没时间了。

C

求出结束状态中的最小值,全部减去这么多,那么结束位置前第一个 0 就是初始位置,暴力模拟一遍就可以。

话说我一开始写的纯模拟,要交的时候觉得不太对劲,然后再看几遍发现有严重 bug ,果断改。

hack 错一个人,好伤心。

D

其实很水的啦。建立两个集合,每次随便取两个点,在这两个点之间连一条费用为其 sum 中较小的值的边,然后将 sum 值较小的那个点删掉,再更新两个点的 sum 。我们必须保证两个集合中一个为空时,另一个大小要为 1 。于是在 sum 相同的时候,删掉较大集合的点即可。

考试时我还脑残地用了 set 呢。

E

看了 YY 了一个思路然后觉得写不出= =于是没写了。虽然说还有一个小时,但觉得 rank 已经可以了(本来的目标就是 div1 嘛),于是就没写了,hack 人去。

这里先挖一个坑吧。

填坑中。

和考场上一样的思路。首先离散化,易知至多只有 9!/(3!)^3=1680 种不同的 x y 坐标对,因为任意一个 x 都要把 n 个点分成两半,其中必有一半是恰好 3 个区域的点数。然后枚举,用主席树判断这 9 个区域的面积即可。时间复杂度 O(1680^2 log n) 的。

还蛮好写的。没啥细节的。

tourist 用的方法好生奇葩,没看懂。

看懂了 tourist 代码之后觉得我就是个奇葩。你不是要维护前缀和么,尽管有那么多次询问,可是枚举垂直于 x 轴的两条直线,再枚举垂直于 y 轴的两条直线,每次你只会查 3 个区域的前缀和。那么每枚举一次 x 轴的坐标对时重新求一遍前缀和就可以了啊,还写什么主席树呢。

我写的 C++0x 居然比 watashi 的 Haskell 还要慢,不活了。

situation

一看 A 不是水题么。5 min 怒 A 。

一看 B 不也是水题么。写了好久= =。 18 min A 掉。

再看 room 里面有人 11min 过了 C ,觉得 C 也不难吧。但我觉得 D 可能可以搞出来,于是搞 D 去。

看了 D 的题目觉得没有思路,返回去看 C ,水题一个我去。差点交了暴力。36 min 。

再去看 D 。随手 YY 了个用 set 维护的算法,觉得也还靠谱,写完一交居然就 A 了 = =。 49 min 。

然后看 E 。在 1h10min 的时候 YY 了一个复杂度无法估计但目测很快的算法,但不准备写了, rank 还是蛮高的,hack 别人靠谱些。

于是一个一个 lock 掉。看 A 感觉太没 hack 点了吧,于是看 BC 。B 成功 hack 一个人,C 的一个 hack unsuccessful 了。

在结束的时候又看到有人 B 写挂了,但没来得及 YY 一个数据 hack ,sigh……

不过终于涨上 div1 ,rating 踩掉大叔了~

others

xiaodao 莫名其妙只过了 A、C ,B FST 了,D 没过 pretest 。

XLk B 被 hack ,D FST 了。不过他的手速给我好大的压力= =||。

hyc rank73 也不错了。

liouzhou_101 D 也 FST 。 D 的 trick 有这么多么。

然后手速蛮快的,还 hack successful 了一个人。如果没有 hack 另一个人,那么应该是 div2 中的 rank1 吧?

rating 曲线啥的,就两次那就算了吧= =