注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

APIO滚粗记  

2013-05-11 22:06:01|  分类: 日记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
啦啦啦,其实我心情很好的说。。。实际成绩比我考场上预计得分好了太多,本来估计只有13分的,最后竟然乱七八糟得了58分。。。无话可说,不过兴奋了我好一会。

首先膜拜所有分数比我高的神犇,你们的水平是我的n倍以上。
然后格外膜拜虐掉了王康宁的超级大神犇——唐翔昊,第三题提答题利用神一般的构造怒切了,全场最神之人,没有之一,跪傻了。如果没有他的话我们这群人就真心滚出了。

下面开群嘲:
那些没上200分的都是一些什么心态?这种,b题没AC还算什么搞OI的。。
分数木有我四倍以上的都是渣渣。
以上是滚粗狗因滚出心情不爽以彰显优越感而说,亦是嘴巴选手的独角戏。

但是我真的觉得上两百的不多实在很不像话了。。前两题对于神犇而言应该都是很容易的题目啊。。一些基础算法的组合而已。。代码实际也不是挺长,就是有点繁琐,但是根据我考场上的逗比经验来看,敲完其实木有很大压力。
不过因为细节滚出也是可以理解的,但是有这么多pretest,应该不会出现往常的那些因为各种小细节丢分的情况。好啦,事实是考场是犯傻的人还是很多的。

还有一些因为实力问题而滚出的,比如像我,唉,不想说了,只可叹技不如人。
下面写写考场上的经历吧。
早餐我没有吃啥,唉,早餐实在不令人满意,所以我也就吃了个卤蛋。面包直接塞包里了。

兴致勃勃地来到考场。结果发现windows里面有vim好开心啊,花了比较短的时间将东西配好了就水了水练习赛,然后被第三题吓傻了。

不管了,考试莫名提前了半小时就开始,于是傻逼的我就开始看题了。

嗯?第一题感觉很眼熟啊,似乎没有多项式时间的算法来着?奇葩的网格图上将一些点合并,然后总代价最小。。。
(后来听xtc说我在前一天信誓旦旦的说绝对没人会考斯坦纳树,囧死了)
一看n比较小,大概状压dp吧。

于是去看第二题了,最小生成树,大概是这个意思。。。稍微想了想,可以缩点,然后大概也是状压dp一下。。。

本着提答题优先的原则看了第三题,结果发现并非传统意义上的提答题,大概得自己构造数据,于是就暂时放着,先看前两题。。毕竟只是APIO的题目 嘛,常规题搞搞应该还是搞得出来的。

法法塔滚出记正式开始:
第一题开始逗了一下,懒得预处理图,以为只需处理出机器人能够走到的点就行了,写完了,结果发现果断不行,将状态转移漏掉了大部分。
然后再想集合确定的时候,内部可以BFS就行了,但是好麻烦啊
最后老老实实将图预处理出来了。。。发现这样的时间复杂度是O(n*2^n*w*h),勉勉强强可以跑过去。。。
于是法法塔就傻逼地又写完了,写到最后dp的时候囧掉了,内存开不下。。。估摸着实际能够到的点数不会很多,所以就开了个map存下dp值。。。
逗了这么久,加上我写代码比较慢,已经过去两个半小时了,交上去,咦,国内数据只过了三个点——but,国际数据第二个点就过不了T_T
仔细想想觉得代码实在不可能有问题,又想了一会,觉得我不会将代码写错。于是得出结论:我的做法有问题。去看第二题。

第二题更坑,秉持着之前的思路,我敲完了缩点。于是剩下的就是选择一些边在生成树上。没有细想,我先将缩完后的那部分代价算出来。。树型dp好蛋疼啊。。。不过没关系,好歹写个dp还是没问题的说。
接下来我就纠结了一会,是用状压dp来选择边呢?还是直接暴枚。
其实我是倾向于dp的,这样似乎比较方便把握情况。暴枚边感觉直接计算可能会达到k^2级别,不一定过得了。
然后发现内存继续被卡。没关系,有些点的k值比较小。
但当我试图将转移理清的时候突然意识到了一个严峻的问题:
缩点是不行的!
因为连接缩掉的那些点的边权是无法等价的替换成一个点或者一个边的。。
完了完了,算法又想错了。
于是就只得将缩点的代码什么都删掉。开始敲暴力,2^k次方暴枚,能骗多少是多少了。
于是大概写了个2^k*n^2的算法,感慨dfs好麻烦。。
于是手测了下样例。
于是发现样例都过不了。
于是发现只有那k条边会算进代价。。
于是发现这就是道傻逼题。
于是又蛋疼了蛮久,发现没时间了。
于是就啥都没干开始看第三题。

第三题我才是逗中之逗。看了下题目,觉得第一个点挺好做的。。于是就做了。
打包打了好久
打好包了只剩下三十分钟(我现在发现我真的好傻,有这时间为何不去做前两题了,果然我对于自己的代码能力还是没有自信)
于是开始看第二问。。。似乎也是挺简单的。。
但是我无论怎么调参数都无法使之TLE。。。太不科学了。。
唉,此时我的渣渣心理素质就体现了。
几乎完全慌了神,于是一直在那儿犯傻地娱乐第二个点,也没抱着过的指望。
考试也就在我的失望中结束了。

算算在国际数据上得到的分——13分。。。完蛋了
顺便问了下vfleaking神的情况——第一题切了
问了下Mato_No1——100+
发现似乎就我一人啥题都不会。。。默默的哭了。
然后食堂里问了下唐翔昊——第三题切了。。吓傻中
似乎雅礼这边都将提答题做了,一问才发现有64分是送的。。。
不想说了。失望地徘徊在北大的校园了。一边好奇第一题这么神怎么可能有算法啊?
一问——吐血
又询问了下第二题
继续吐血中。。。我回忆起我为何纠结那么久的原因了。
然后第三题翻出题目看了看最后两个点:
T_T

唉,所谓实力问题。。。其实其他都是次要的。至少反映出了我敲代码的速度还是太慢,不然也不至于最后没时间看提答了。也不至于因为看错题而纠结蛮久。。
真正的神犇能够看错题之后顺着错误的题意将难度加强好多倍的题目很帅气地切掉。。。
而我这种码代码都码不完的傻×只能默默地滚出。
是也,滚出才是我等的夙愿,作为弱菜的代表,在此给所有虐场的大神跪烂了。

再简单说说后面的事吧:
等成绩时稍稍完善了下第二题的算法,严格证明了下正确性,发现没法做到比k^2*2^k更优,结果得知王康宁大神用这个复杂度过了。。
听说不少人第一题用了SPFA,不知道是啥心态。。。又听说有人被第一题的环给坑了。
最后我的得分为35+20+3,不能更逗。
讲题时我没怎么认真听了。。。第三题时被唐翔昊的神构造吓傻,果然霸气威武。
随意询问了几个人的成绩,都是140+
湖南似乎考得不是很好?难道唐翔昊是最高分?算了,这问题和我木有关系,只是很高兴最终没有垫底。
话说我一直不知道Mato_No1是谁,当初他在冬令营上各种刷存在感我感觉挺逗的,主要是语速太快听不清楚。。但是得知真相之后各种跪烂。
呜呼哀哉,歌以咏志
=================================================================
这是第二天所加上的部分:
睡了一觉起来发现心情不是很爽,感觉对不起国家对不起党。。。。
真的,因为这种原因滚出的不tm都是傻逼么?
感觉实在无话可说,自责之心溢于言表
难以理解我为何会在考场上犯这种错误的说,明明我也很仔细地看了题啊。。
心不甘啊,明明知道考后的一切言行都木有了意义。。。被傻逼题坑了心情不爽,现在正在郁闷中。。
问题是有没有啥教训可言,感觉一切都好好的,状态也是极好的。。。但是结果还是滚出
无语
=================================================================
回家后敲了下前两题,由于没有数据,所以没有测试
但是敲完两题所用时间是不到两小时的。。。
已经是不能改变的结局了
  评论这张
 
阅读(452)| 评论(8)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017