COCI 2010/2011 #5

这次比赛难得那么好的一个AK的机会。。然后我SB掉了。。。

前2题无视。。第三题从小到大一个个枚举过去。。。N^2就可以过。。我写成了N^2LogN。。然后最大点居然只要0.04s。。。这。。。

第四题一个简单的dp。。状态分3类就可以了。。

第五题可以线性。。具体就是直接做开始是很困难的。。可以考虑从中间往两边扩展。。那么搞出所有极大区间。。

然后用一个栈扫描一遍就能得出答案。。。

第六题其实很水啊。。把版按照棋盘黑白染色。。可以发现两个颜色是互不影响的。。就转变成了两个经典的矩阵染色问题。。

这个染色问题显然可以2d线段树。。不过我觉得这个常数过大还是用线段树扫描一下吧。。。。

然后处理一下Load和Save。。可以发现其实Load和Save只是意味着有些操作是没用的。。

删掉就行了。。。

然后我处理错了。。。只有13分>_<。。。。。。

比赛结束了按洲妹的改了一下就AC了。。。。。。擦。。。

经验+总结:

以后参加比赛都要写写总结之类的。。。这样才能吸取教训嘛>_<。。。首先是第3题。。我犹豫了半天要不要改N^2LogN的算法。。因为我觉得不怎么可能有数据能卡这个。。。这浪费了不少时间。。非常的不应该啊。。应该在写题目的时候就估算好复杂度。。直接写N^2的多好>_<。。。还有第5题狂对排了一下。。感觉上就能在比赛的时候放心不少。。
最失败的是最后一题。。这说明细节是非常重要的。。一些重要的细节问题一定要多加深思啊>_<。。。。
然后直接在脑子里自以为是的想一下就写程序是很不行的>_<。。应该在纸上多画一画之类的。。。

还有感觉自己代码能力好像还过的去。。但是平常写程序的时候变量名称有时候都要考虑一会儿>_<。。而比赛的时候无疑是很浪费时间的。。。但是混乱的名称又很那啥。。。应该组织一下自己的各种变量名称了>_<。。。

9 thoughts on “COCI 2010/2011 #5

  1. 第五题直接做也不困难。。就是预处理向左向右最远的区间。然后(i,j)区间充要就是左边往右>=区间长度/2,右边同理,然后维护可行右边就可以做了

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>