NOIP2018游记

蒟蒻的姗姗来迟的游记 由于没有爆炸也没有考得多好，所以就叫游记吧。 DAY -N 虽然这只是NOIP，但内心还是超慌，毕竟这届竞争力可强啦，而且也是最后一次认真打NOIP了！还有一些崛起的，和脱离中考回归信息学的新高一。在家打了几个板子，打了ZROI的模拟赛，才rank18，220分，掉了rating，好菜啊！感觉吃枣药丸…… DAY 0 去试机，这次又在本校（好像没有哪次不在），试机时，本考场有几位同校dalao总是喜欢围观我，感觉药丸。旁边几个bbtjb中学的老师还在教他们“小鱼会游泳”“小玉家的电费”，2333 晚上调整好心态了，反正是条咸鱼无所谓了。 DAY 1 早上刚进考场想吐，感觉凉凉。进了考场，打开题面，T1好像有点像NOIP2013（出考场才知道这是原题），我还傻缺到不会贪心，写什么逐层覆盖，计算段数，15min写完，过了大样例，不管了；T2，看起来好神仙，猜个结论是倍数问题，没过大样例，又猜是要用前面的数表示出来，看数据范围ai<=20000，猜要用背包，直接O(Tn^2ai)，对于每个物体，计算小的能否将其表示出来，预估80，100分暂时不会，先弃了；T3，什么神仙题，m=1是树的直径，写了过了样例1，不管了。一条链是二分，初一时学过这玩意，写了造组小数据，手算是对了，不管了。菊花也是二分，差不多是贪心匹配问题，随便写写就过了，不管了。还剩2h，现在预估得分100+80+55=235,235乘2是470，去年这分好像是现役第9……看到T3子任务是二分，自然猜标算也是二分，先二分答案，再记录top数组表示最上方的值，然后和菊花一样的匹配，再暴力枚举把哪个记为top对答案没有影响，调调就过了大样例，正解是O(nlog^2)？而我是O(n^2log)。看看好像能85。 检查程序和文件名，发现没有错，不过发现T2有一层循环是废了，然后就删了，检查一下，大样例过了，不管了…… 估分：100+100+85=285 DAY 1.5 下午得知一千个AK的，那个T3不用暴力枚举改成二分就行，无数个255的，是个正常人都200+，身败名裂，不过差15分不虚，一定坚信自己能翻盘！ 晚上依旧睡得好，心里没想太多，就当是自己稳了一半吧。 DAY 2 听说wrq dalao没有AK而且才240？高一why、gyf都是255。本校没有一个AK的……这么说我考的也不算差？ 感觉今天会很难（正如NOI2015 DAY1特水DAY2难一样），感觉药丸。 打开pdf，果然画风突变，感觉T1比昨天T2难，字典序最小？一看后面：m=n或m=n-1，还好。m=n-1就是一棵树，直接贪心，10min写完，60分到手，总分能上300了。m=n，对每个点（除了1号点）总是从1条新边扩散的，于是就写拆边，发现小样例错误，哦！还要判断连通性，改了一发，样例全过，不管了。T2好神，T3好神，还有2h40min，看如何分配时间。首先写T2的20pts，简直像送的分，枚举每个点颜色并枚举每条路径，发现样例跑过了，不过这都写了快1h（我太菜了）。然后根据捡大分的策略，直接干T3的44pts，暴力普及组DP，很快就过了。 现在还有不到2h，目前初步估分100+20+44=164，总分能上400分了。然后感觉T2的n<=2和n<=3有规律，猜一发n=2是一直乘3（因为一列3种可能的），打表到2 5发现是对的，写了n=2的分，然后n=1就不用说了是2^m，也写完了，n=3，打到3 6的表发现也是一直乘3（感觉所有都是一直乘3？），打上表，跑不出后面的，于是写了if(n==5&&m==5){puts("7136");return 0;}就滚去看T3了，差不多还有1.5h的样子，估分100+65+44=209，带上昨天才494~~不太行（然鹅都高二了我的目标肯定至少是500+吧）~~。正解好像是动态数据结构的样子？但我不会打就算了，老老实实看部分分。先是最水的"B1"，直接暴力修改一个点就行了O(n+100m)，很稳的复杂度，造一组数据对比一下过了，不管了先拿下这8分再说。再看一条链，也没啥思路，为啥都要做呢？分开看："A1"：强制选1号，从中间某处断开，可以两头DP，这有8分；"A2"：选相邻，如果都不选puts("-1")，否则还是双端DP拼起来，这有12分。总算放心了，100+65+72=237，加上昨天522，一个不错的成绩？感觉wrq应该不会翻到我上面？ 出来问下本校的，why估计194，wrq好像T1凉了……好像都不太好的样子（至少没有昨天好）。 DAY 2~6 焦虑等成绩，全国考的都很高吧？AH代码下发效率就不吐槽了。 DAY 6.5~9 晚上代码下发了，测一下吧，ZROI是535，洛谷是531，牛客是532，学军是518，所有测试点取min是505……现役选手被tyx较稳的541吊打，但比其他现役都高？（反正tyx他们有School Kill管他呢！） DAY 11 咕到早上出成绩，100+100+90+88+65+72=515，D2T1数据太强了，本以为能成为迄今为止唯一一场没有任何遗憾的比赛，结果最终还是有一些遗憾……弱省现役第二，果然被tyx大佬的541吊打。还有初三的514？tql！（不管了反正他们学校初中生不能参加省选233）感觉ASDFZ有点凉，ASDFZ外的果然比以往强多了…… 本以为这场比赛很完美，但还是有瑕疵，比如D1T3想到做法栽在二分,D2T1的被卡常，要不然就537了，不过说这些也没用，分掉了就是掉了，水平低就是水平低啊！ WC应该没啥问题吧，先好好准备WC吧，不要像今年SC一样无约滚粗吧…… UPD 2019-3-5：真的~~无约~~废约滚粗了。。。都快忘了这篇文章了。