Noip2014 Summary

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

今年的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都花在这一次比赛中了吧……)

AP SSC History Quest 说:
2022年9月15日 23:37

History can guide learners to see trends and processes from a broader, holistic perspective and to understand them. Through History, they come into contact with other cultures and societies and in this way they gain a more holistic understanding of the contemporary world and their place in this broader context. Telugu Medium, AP SSC History Question Paper English Medium & Urdu Medium Students of the State Board can download the AP 10th History Model Paper 2023 Pdf with Answers designed based on the revised syllabus and curriculum of the course. Class teachers and leading institutional experts are designed and suggested the Part-A, Part-B, Part-C, and Part-D exams like SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 along with Assignments.


登录 *


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