Noip2014 Summary

VictorWonder posted @ 2014年11月10日 09:57 in 总结 with tags Noip , 762 阅读

今年的Noip总体来说还是挺不错的,感觉有点感冒了,day2起床的时候喉咙有些难受(其实day1晚上喝完咖啡就感觉喉咙难受了),略微有些不爽。

按照惯例,还是要先发一下题解。

Day1

T1  话说,如此之长的题目到底是在闹哪样啊?一眼看过去,应该是求出na和nb的最小公倍数,然后再取模,再暴力……等等!这数据范围到底是怎么回事?200的数据范围……打个表然后再暴搞,于是就开始各种if,出来之后被大神Claris狂D,其实只要开个数组存一下就搞定了……

T2  听说有人由于取模的问题爆零了,节(xi)哀(wen)顺(le)变(jian)吧。刚开始的时候觉得要用树分治搞,不过太麻烦,所以就弃坑了。暴力还是很简单的,对于每个点暴搜,搜两层,如果不是菊花图的话,极限数据也是能秒过的。但是,今年Noip全国征题,数据应该不是随机的,所以必须要想别的做法。我开始的时候想到了两种情况,一种是某结点子树中与其深度差为2的结点,还有一种是其父结点的父结点(爷节点?),结果对拍的时候各种出错,后来发现没有讨论其父结点的其他子结点的情况,深搜一遍求出各种值然后再直接搞一下就行了,时间复杂度是O(n)的。Claris一直说这题太水没意思,咱只能默默膜拜了……

T3  刚看到这道题目的时候就吓尿了,Claris出的Mike Cup #14的T3也是Flappy Bird,不过Claris出的是答案提交题,而且每次只能点一下,但确实差不多。当初我是暴搜搜出来的,标解是DP,所以现在这题估计就是DP了。果然如此,先随手打出了O(nm^2)的DP,很明显是会超时的,随便YY一下就想到了O(nm)的做法(考虑由什么状态转移成为现在的状态,一共就三种情况)。感觉内存有些大,于是又打了滚动数组,然后就是不停地对拍出错,由于打了滚动数组,调试起来各种蛋疼,搞了两个多小时,本来打算放弃,只交最初的程序的,没想到还是在最后十分钟的时候搞了出来,大数据对拍了一下,感觉应该是没有问题的。晚上在酒店,Claris说,这道题目对游戏的介绍绝对是从百度百科上扒的,因为他当初出题的时候也是去百度百科上扒的,有一句话记得特别清楚:“游戏便宣告结束”。

 

Day2

T1  看上去就是前缀和,后来发现竟然暴力可做,不过打都打完了,以防万一,最后还是对拍了一下,结果发现暴力反而各种出错。幸好最初的时候打了前缀和版本。另外,Claris表示他在最近刚做了一道一模一样的题目,好像是USACO的(也可能是POI的,具体忘了),那题的数据范围是一百万,要用扫描线过……(咱们还是忽略这一点吧)

T2  最短路问题,预处理一下就可以了。于是建了个反图,广搜搞了一下,接着再用SPFA求最短路,出来之后又被狂D。Claris表示既然边权为1,广搜就行了,如果出题人丧心病狂一点,完全可以卡掉SPFA……

T3  高精度?实在是没有动力搞,然后就想到了hash,先用10^9+7取模,再用秦九韶算法搞一下(幸好我Day1晚上看了Claris的数学总结),但总觉的会有问题,10^9+7实在是太常见了,所以就随机选了三个六位的素数,应该不会被干掉吧?这素数我是随机从素数表里选的,自己都不知道是怎么搞出来的……但是最大数据还是要超时,就拿70分好了,到时候看标解到底如何。另外,Claris一直坚持本题是CTSC某道叫做因式分解的题目的加强版,对此我不作任何评价。

 

今年的比赛发挥还是挺正常的,但愿没有出什么纰漏。感觉试卷过于简单,根本没有区分度,不过不管怎样,反正都已经过去了。不过,要学习的东西还是挺多的,接下来要开始走上Claris去年走过的道路了,希望在接下来的一年里能够有更大的提升。

 

Updata:最后拿了570分,和一大帮人并列第5……不过还是非常高兴,这次竟然考得这么好,本来以为要二等滚粗的说(不会RP都花在这一次比赛中了吧……)


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter