The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

果断转载 哈尔滨赛区总结 by Latsyrc @ SYSU_Vermouth and zhshzhen (MikeZheng)

      前一天晚上12点就睡了,睡得不是很好,做了几个梦,醒来了几次,其中梦到cyl卡F
题,然后很水的B题最后才过。没想到梦也成真了,只不过题号有偏差。

    鉴于集训的时候我们队错误较多,加上热身赛的观察,我们并不觉得自己速度上有太 大劣势,于是决定采取谨慎的策略,每题提交前再看一遍代码,检查检查。

    还是老策略:我从前往后看,kb看中间,cyl看后面。看了A题,发现看不懂,再看了
一遍,还是不懂,这是kb跟我说C题是3D凸包,求面数,大水题,果断要过来,但是没有马
上开。继续读B题,感觉是一个贪心,跟kb说了一个方法,kb也跟我说了一个方法,突然发
现我们的方法截然相反,于是我丢给他想,果断上去写C题吧。后来证实我们的算法其实是
一样的。写C题的时候看了一下board,发现有人过F,问了问cyl,他说他在规划了,我说
随时推我下来。之后他利落的过掉了F题。然后我继续写C,cyl接手B,kb在想E。经过他们
讨论后证明了算法正确性,cyl上机,提交,结果错了,看程序,发现了他一个很弱智的错
误,修改后就过了。我利用空闲断断续续的写好了C,由于很容易错,于是打印出来检查。
kb上去写A,其间kb跟cyl说了H的做法,cyl规划好了构图方法,让我过了C后帮他敲一个费
用流的模板。在59分钟我很利落的一次过了C题,也是全场第一个。之后很长时间都没有人
过,第二个应该是石头哥。之后kb的A题返回wrong answer,他跟cyl讨论了一下,发现对
题目的理解有问题,迅速修改。我和cyl也在kb改A的时候讨论好了D题,一个裸的dancing
 links,商量好构图后,决定让我来写,其实我没有太大的信心,因为这个东西是在来哈尔滨的火车上学的,还从
来没有写过,同时还讨论了已经很多 
油ü腅题,结果不会。很快kb的A过了。我帮cyl敲完了H的模板,他构图写进去也很顺利
的通过了。就这样前2个钟我们过了5个题目,手头上还有2个题目在做,形势不错。

    然后让cyl暴力E打表找规律,毕竟很多队过了,不会太麻烦,其间我一直在写D,写得
很纠结。事实上当时我们的排名一直在往下掉,我敲D的时候手一直很僵,头很晕,补了一
块巧克力,好了一点。最终经过努力,kb还是在209分钟过掉了E题。我们终于缓了一口气
。在cyl的帮助下,我的D也搞定了,测了几组简单的数据没有错,我问他要不要提交,他
说交,怕什么?说实话我是没有任何信心的,首先这个东西不熟,其次觉得自己写得很乱
,毕竟200多行的代码,错误在所难免,最后就是这题只给了1秒的时限,感觉蛮紧的。结
果居然返回一个YES。我和cyl都叫了出来,顿时士气大振。在我调试D题的时候,kb和cyl
讨论了J,没想到什么好方法,用四边形不等式只能优化到O(n^2),肯定不行,但是没有题
目,还是让kb硬着头皮上了。然后cyl弄I题,kb说自己的肯定过不了,于是让我再想J。我
列了一条式子,发现具有单调性,然后跟kb讨论了一下,被他质疑了,其实我还是很肯定
的,于是还是给他写完吧,我继续想。他提交毫无疑问返回了超时,我也在书中翻出了类
似于我列出的那条式子的式子,还剩下30分钟,时间还足够,于是果断抢过机器,利用kb
之前写的预处理,直接把dp写了上去,写完后他们一起帮我查错,提交,答案错了,再检查,发现打反了一个符号,修改,再提交,一个大大的绿色的YES。 我大喊了一声:“哥立功了!”。真是内牛满面。然后我就果断打酱油了,他们两个在讨
论那个积分题,后来才发现算错了一个东西,不够时间改了。最终定格8题,5题一次过的
,2个wrong answer,一个TLE。其中那两个wrong answer完全可以避免。

    后来跟石头哥他们讨论才发现G题他们的方法跟kb想的一样,kb觉得时间太紧于是没有
做,实在太可惜了,最后10多分钟写一个SPFA也不是什么难事的。其实想想卡E和D的期间
上G也是一个不错的选择。总结这次比赛,最大的败笔就是E题,一个毫无疑问的大水题,
我们被卡了很久很久,浪费了很多时间,似乎我们的3个队对于这类题目都很水,还得加强
锻炼。或许如果比赛前期就丢J给我,我们对于时间的安排就会更为合理。至于我个人的发
挥,我比较满意,两个200多行的代码都是1AC,J题也顶住压力绝杀成功,事实上08年在北
京我也是最后30分钟绝杀一道单调性dp的题目。

    说说队员间的配合。我们队算是磨合得比较好的,其中D题的构图是我和cyl讨论出来
的,B题的正确性是kb和cyl讨论出来的,H题算法是kb提出,模板是我抄的,其他代码由c
yl完成。J题kb提供了预处理。

    最后bless 1,2,8队在下一站天津赛区中再创佳绩!
--




其实结果就一句话:“混水摸到鱼了。”

农历八月十七,中秋节后,经过漫漫四十多个小时的火车,我们终于到了这个传说中冰天
雪地的哈尔滨。下火车,天气好,晴朗阳光下伴着瑟瑟凉风,有点冻……

星期天早上九点多,比赛正式开始。
开ball,我调机器,然后从前看,石头哥D开始,训哥后面看题。
看完A后,我发现题目规模巨大,马上淡定了,心想应该不用什么复杂的博弈,但还是放了 下来。
这时,石头哥看完C、D,说D用在火车上新学会的dancing link可以搞搞,C是纯模板题,
然后果断让位给石头哥拍C模板。
我继续看B,好像原来B更水,几番思前想后,我还是直接抢断石头哥的C,自己敲B,因为
B真的好像很水……B的做法是两次排序然后for一下,直接过了。
刷board,有人过F,chyx也跟风很快过掉了F。
再刷board,发现A、E、H都可做。换人,石头哥继续敲模板。训哥接过他的菜数学题E,无
奈说了好多次不会做……囧。不管了,于是我拉他过来小讨论了下A,发现真的挺水,就敲
了,就过了……
剩下E、H。E是数学题,我想还是训哥继续纠结一下吧。H是明显的费用流,我想好建图后
,上模板,直接又过掉……看来今天我的手风还是挺好的。
E嘛,训哥还在说不会做……囧,好奇怪,我推了下居然好像就推出来了,又不管了,抢过
机器,试了下,发现样例都错了,改了下,就过掉了……

此时5题,全是1AC,华丽了……
期间,石头哥的C交了,然后错了。叫他加上判重点、共线、共面后,还是不过……无奈之
下,训哥作为解放出来的生产力,去敲I了,说不想浪费机时,先敲个输入输出。
石头哥说应该C没错的呀,但还是先放下了C,接过训哥给的G,说好像半平面交能做……我
对着石头哥C的程序和石头模板,发现真的没敲错,不过有个新加的判共线的地方很诡异,
问之,石头哥说傻B了,一改,救过了C,搞了这么久的C终于过掉了……石头哥状态不佳啊
,囧。

6题在手,但比赛时间还有好多好多,此时成绩并不足够。
到了后期,训哥一直在纠结I,说之前一直在研究这个数值积分,应该没问题的啦,但还是
过不了……换模板,发现模板上的精度更水,就又继续埋头纠结了。
其实我一早就接过训哥的J,但想起上次百度之星写过一个类似的当时写得我很纠结的单调
性DP,马上就颓了……石头哥说可以四边形不等式优化一下,发现还是TLE,然后我就不得
不重温上次的悲剧了,一边手写J的单调性DP,时不时一边看看石头哥的G。
话说石头哥和训哥讨论后,拿出算法导论,发现G可以差分约束,然后猛男般地上去敲G…
…改了几个小bug,加了一个优化后,就神奇地过了G,无敌了……
训哥的I在最后不知道怎么根据函数的特点改变了积分的方法就过掉了,同样离奇……

比赛结束,我的J,写到最后调出样例和几个水数据之后一直交不过。我的错,小悲剧了…


总体,中大的三个队成绩都挺满意。三队Vermoth第四,我们四队Vodka第五,都金了,六
队波本也银了,很好!


下一站,杭州,坐等送死。
--

posted on 2010-09-26 23:36 abilitytao 阅读(322) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理