Codeforces Round #245

。。。今天hnoi结束了……
听说好多人退役了。。。
也拉不到人一起愉快地打cf了……
说真心话,我觉得这次hnoi很多人实力都比我强……却退役了。。。
oi随机性太大了。。。
总之祝加油吧……

不扯了……
现在的状况有点感动。。。网络是靠手机开wifi热点供的。。(真·靠手机打cf
连个书桌都没有。。。
这场还是紫名爷的round……想想就怕。
看起来要跌紫了……

update 23:34

凑推迟了十分钟,浪费表情啊……

update on 比赛刚刚结束时

智商低没活路。
开局写错了A,本来可以4分钟过的。
然后听说D是裸题,结果就往斜率dp方向想,想了半小时后无果,发现是平面最近点对裸题。
当时就想骂人了——我没最近点对模板……以我的代码能力写几何题简直是作死。
找了半天模板之后凑了一个交上去(用浮点数运算的,简直了)
然后看一大波人水过了B,结果我看了一下发现果然是手速题,然后写好交上去wa on pretest 2
思考了一下人生感觉是我看错题了。
然后到处找人问题意。
最后得到的结果是:比赛中间有插播消息说那啥两个人的交点必须只有1个。
然后那个信息我不知道为啥没收到。
当时我就卧槽了。
总之就成了房间里面B分数最低的一个了。
智商低无活路。

然后看C,感觉叶子 挺少的 ,可以用括号序列描述这棵树然后爆搜。

写了十分钟勉强过了样例,但是弃疗了,因为一看就知道错误百出。

然后反应过来可以直接裸着搜,乱搜……因为非叶子/根只有10个节点。
但是因为想D的时间过长。
所以就没有时间码了。

最后就在毫无cha点的几题中找人cha的过程滚粗了。

顺便比赛前立的flag:

Foreseeable 2014/5/11 23:27:09
这一定是unrated的好兆头
Foreseeable 2014/5/11 23:28:15
跌紫计划要失败了的样子。。。

最后一句话:
我tm最讨厌手速场了

打完了我就去睡觉了。。毕竟醒来还要旅游半月。。。

update on 5/12 18:18

实际上今天还是挺愉快的一天的。
一大早就起了床(虽然刚熬夜过)
然后坐裘老师的车去了宁波。
路上发呆发了一两个小时。。。
然后就到了。
然后遇到李建老师……
他居然告诉我昨天cf fst了好几题,大跌了rating。。。。

然后去吃午饭,吃完之后上cf感受了一下。
发现光荣地成为了紫名狗。

这个故事告诉我们:不要乱立flag。

题解:

A

忘记题意了也懒得看。5分钟内过不了的面壁5分钟去吧(我已经面壁5分钟过了= =)

B

注意你要找到的路径必须仅有一个交点,那么假设交点是在(i,j)
显然两条路线的交点只有这两种可能:[(i-1,j)->(i,j)->(i+1,j),(i,j-1)->(i,j)->(i,j+1)]或者[(i,j-1)->(i,j)->(i,j+1),(i+1,j)->(i,j)->(i-1,j)]
然后dp处理出以四个角为起点时候的最大权值路径就好了。
注意一下交点不可能在第1/n行或第1/m列。
我是因为这个错的= =。。。
当然要避免这个也不难。。。。

C

因为非叶子节点的子节点数要大于1,所有非叶子节点最多只能有n/2个。
爆搜即可。
状压dp也可以做,但是我没仔细想。

D

裸的平面最近点对。
实际上暴力for就能过。
如果追求优越复杂度的话,写分治就好了。
听说baidu到的模板第一条是错的。
我当时是google的……因为懒得把double改成longlong而挂精度了。

E

不知道为何当时场上没想出来。
实际上可以先把线段看成固定一个左端点的射线。。。
很容易发现射线的情况很好做,只要2i-1和2i的颜色不一样就可以了。
然后线段和射线也没啥区别,因为线段能拆成两条射线,要求两条射线颜色不一样。
所以拆线段建图+二分图染色就可以了。
顺便那个无解输出-1是骗人的。
很显然这个图是二分图。

Comments

comments powered by Disqus