Codeforces-168

Posted on 2013-02-21 In CS/Math , Codeforces Disqus: Word count in article: 791 Reading time ≈ 3 mins.

TCF 一起跌，再也没有生活的信心了。

Solution

排序后贪心即可：如果没选 a[i] / k ，那么就可以选 a[i] ，set 维护一下够了。

考场上我写的很奇怪的算法。YY 错了算法，我以为把所有的数变成和根一样就可以了 lol 。于是这个题变成了一个很简单的 dp 题，方程为 f[i] = \|v[i] - v[fa]\| + max(f[j]) 。

于是开小数组 FST 了。

于是考后重交一次过了 lol 我该如何表达我心中的 ** ？我交的时候还是最短代码呢= =||

正确做法是分正负两种情况讨论即可。

感觉 C 和 D 的分数分配不合理啊。

YY 的一个结论：最后消失的洞要么是被某个锐角三角形围起来了，要么是被一个矩形围起来了。

考虑原图的所有三角形。首先钝角三角形不会对答案作出任何贡献（围成一个 hole ），锐角三角形会一定会作出贡献，直角三角形可能会做出贡献。

对于锐角三角形来说，肯定是用外心更新答案。对于直角三角形，我们找是否可以构出矩形，如果可以，用矩形的中心更新答案即可。

我会说我随手写个 sort 过了 pretest ？

正解就是拓扑图搞搞。把每一行 sort 一遍可以得到若干个元素的相对大小，于是构出一个拓扑图。然后随便求个拓扑序就可以了。无解对应着没有拓扑序。

看着这个图就让我想到 CodeJam 的图啊，于是我就没做了。

A 水题秒掉。

B 居然不会做！于是 YY 了错误算法居然还可以错 pretest 。xwlj 数组开小 FST ……然后重交一次发现可过= =|| 最后写 solution 的时候发现这个算法是错的 lol

C 感觉半平面交乱搞一通。放一放吧。

D 第一想法是用平衡树维护拓扑序 = =|| 觉得略麻烦。灵光一闪觉得可以直接 sort 啊，怒 sort 过 pretest lol 。

看了 E 的图觉得毫无兴趣回去看 C 。

哇 C 感觉就是 Voronoi 图乱搞一下啊。不会 V 图于是半平面交吧。最后 O(n) 的半平面交懒得写于是写了 O(n^3) 的半平面交= =|| 然后似乎整个算法都是跪的。

System Test 之前我是 #3 ，System Test 之后是 #300+ ，人生大起大落真是太刺激了。再这么下去小号连 div1 都不保了啊。

XLk 你说你不想做了于是居然和 xhm 开黑这不欺骗我感情么！

Petr 作为唯一一个交了 E 的人还 FST 了。

liouzhou_101 过了 ABD ，D 手速快于是 #14 怒 +60 于是总 rating 虐我了。

lyd ABD #30 （感觉 ABD 大众分啊）

xiaodao ABD #32 （+1/-2 相当于啥都没做 = =||）

好吧 xhm 的两个号也都红了，发现自己真是废啊。