NOIP2018爆零记

### Day 0 洛谷打卡，中平。 上午先最终确定了试机时的测试项目。我把LOJ的那一套测评测机性能的代码拷了下来，先在校内的评测机（和去年NOIP评测机配置相同，双核速龙）测了时间，打算试机的时候测一下选手用机的速度。（可能真的是被毒瘤出题人卡常卡怕了。 给几个没听到Xeonacid讲分块的高一学生补了一下分块基础。收拾收拾机房里的东西，感觉要退役了。 下午到哈工程21号楼试机，蔽校高二似乎是到机房最晚的。。。在门外等了一个多小时，终于轮到我们进机房。 CPU：i5-3470，内存4GB，键盘反人类到无法形容。U盘一插：不能挂载SuperJvRuo 可能是因为我U盘的文件格式是exfat，ubuntu需要装点什么才能挂载。借了Xeonacid的本子（雾）和U盘拷贝代码，完成了性能测试： | 项目 | CCF老年机 | 哈工程选手用机 | | ----------- | ----------- |----------| | T1循环1e9 | 724 | 280 | | T2欧拉筛5e7 | 567 | 366 | | T3Floyd1e3 | 2076 | 1114 | | T4```std::set```1e6 | 1007 | 540 | | T5```new int```2e7 | 1195 | 658 | | T6-1内存访问和缓存（随机）$2^{25}$ | 600 | 501 | | T6-2内存访问和缓存（随机）$2^{25}$ | 655 | 437 | | T6-3内存访问和缓存（连续）$2^{25}$ | 111 | 54 | | T7-1取模（模数宏定义）1e8 | 2369 | 1026 | | T7-2取模（模数为变量）1e8 | 2373 | 1010 | | T8浮点数运算2e7 | 1094 | 5876 | | T9-1CPU流水线和循环展开$2^{30}$ | 1328 | 631 | | T9-2CPU流水线和循环展开（手动展开）$2^{30}$ | 1159 | 510 | 嗯，各位同学一定注意常数。你非要问我那个浮点数是怎么回事，我也不知道啊，我测了两三遍都是这样，NOIP又没有毒瘤计算几何，在乎这个干什么。 比较有意思的是电脑里有codeblocks（可是这和我一个vim用户又有什么关系呢:wq 然后就可以回家颓了。开QQ空间看看。看到这个： NOIP考点居然是交大附中... 蛤？我初中同学在西安交大少年班学OI？问了一下小姐姐的OI之路，人家高一弄数学建模，现在转战OI。高三？少年班没有高三。高中课程学完之后直接就进西安交大了。我一边为OI而努力，一边为文化课担忧，真的很羡慕像她这样没有升学压力的生活。 ### Day 1 洛谷打卡，中吉。 前一天雨夹雪，以为早晨会堵车，7点多就从家出来了，不到7:20就到哈工程了。和神仙们谈笑风生了一会儿，发现大多数人的打卡都是中吉，于是我们开始膜那些打卡大吉的神仙。8:05进场，发现这个机房的配置和昨天的机房完全不一样。。。试试键盘，默写vimrc，等待发解压密码。（这个键位真的是反人类啊，```\```竟然在```=```和backspace之间，backspace这么小，都把我们当成写代码不用删的VCode吗）对着屏幕发呆的时候，眼前仿佛闪过了这一年来OI生涯的一幕幕景象，真的很舍不得机房呢（泪目 8:30准时开考，密码：飞雪连天。（还记得去年的D1密码是不忘初心 打开题面，先看看第一页：i7-8700K？32GB内存？三道题都是512MB?老爷机变少爷机了？今年大概不需要卡常数了（感谢CD类选手们的贡献，终于换评测机了 那我昨天不是白测用时了？算了，先看题。 先大概看了一遍题意，第一感觉：T1似乎很水的样子。。。T2什么鬼啊？T3二分加贪心check？ #### T1 并没有看出来这是原题，但还是秒出$O(n)$正解。一遍过编译，测样例直接水过。看了一眼表，8:45。 Update：听说有神仙被题面里的“首尾相连”卡了，神仙以为是环 #### T2 仔细看看T2，简直就是小凯的诱惑（雾）啊，突然想到上周膜你赛的一道最短路优化背包，还有这道初中神仙的最短路题：https://blog.csdn.net/jpwang8/article/details/82660425 ，又想到Day-1洛谷日报的最短路背包，感觉应该是要用这个科技。最短路上的每一次松弛都改变了使用的币值，跑一遍Dijkstra，看一下使用了多少种转移即可。 写了一发，小样例过了，大样例从第4个开始就听取WA声一片。 想了一会，9:30的时候，突然意识到，为了保证使用的币值种数最小，应该排完序再跑最短路。而且如果转移使用的币值更小，应当使用更小的币值去松弛。 改了一发，飞快地跑过大样例（这个大样例好水）。看了一下时间还没到10:00，心想T2不应该都是思路很正的题吗，为什么会考这种东西，是不是我想复杂了？ #### T3 显然先二分。想了几种贪心方法，都被自己Hack掉了，已经10:30了，敲个暴力先。 10:40敲完直径，10:50敲完菊花图，11:00敲完一条链。 （假装有）255分了，应该还可以，Day2不爆炸，应该就不会退役了吧（雾 草纸上画了半天也没想出个复杂度正确的check，看一眼时间已经11:30了，检查一下三道题的文件读写，顺便最后测一遍样例。 T1正常。 T2。。。。。。段错误？卧槽，哪里有问题啊，我没时间调了啊！先注释掉文件读写试试？————测试正常 ？？？ 折腾了半天，突然发现我把T2的样例拷到了T1的文件夹里，怪不得会段错误，真是吓死我了。 T3正常。 行吧，离结束还有5分钟。等待考试结束。 #### 考后 HL仍然是用U盘收取选手代码。三个U盘还有一个出了点问题，总体进度更慢了。 等待的时候和右边的同学聊了一下。他是牡丹江一中的学生，一听说我是哈三中的，直接把我当成大佬。。。然后他问我：神仙您T2是怎么做的？于是我就介绍了剩余系建图的思想和最短路优化背包，他当时就吓傻了。。。他说他只会n=2的情况。 12:50多的时候才拷完代码。三道题里我最不放心的当然是T2，先问了一下坐在左前方的Cris神仙，神仙听了我的思路后一脸惊讶。出考场门就碰见老张，问我今天的题怎么样，我：T1水题，T2不知道自己的做法对不对反正能过大样例，T3打了55分暴力。 下楼又碰见问Ubospica神仙，咨询了一下T2，神仙说：完全背包啊！ 对啊，是背包啊。 对啊！不就是背包吗？从小到大排序，跑个完全背包不就行了吗？$a\leq25000$，我TM为什么写了个最短路优化背包啊？ Ubospica问我T3的复杂度是多少，此时场面一度十分尴尬。 然后就听他们交流T3做法，这个神仙刚说了自己的$O(n\log ^2n)$乱搞，那个神仙又说了自己的$O(n\log n)$贪心。。。感觉全场都AK了啊，就我退役稳了。 ### Day2 洛谷打卡，大吉。 比昨天晚去了十几分钟，在机房外的大厅里遇到一个工大附中高中部的同学。去年他拿了省二，今年奔着省一考。他说他昨天T1的代码不知道出了什么问题，输出的一直是一串地址。我问他是不是输出的时候在变量前面带了```&```，他说输出的不是这个地址，是文件的目录。。。 ~~dalao，您能教我怎么输出这个吗？我也想学~~ 这位同学初中也是在工附，初四的时候通过贯通部进了高中部。他说去年的时候高中部有十多个人学OI，当时请了师附的老师来讲课。后来学生少了，他就只能去师附听课。工附高中部主抓文化课，他只能周六周日去师附听课。几周下来就跟不上师附的进度了。感觉在这样的环境下学OI也是挺惨的。 我也只能安慰他：“Day2大概和Day1差不多，题应该不会太难，您今天拿个200+，加起来也稳拿省一了啊”（Flag 1 算下来，Day1大众分255，Day2大概骗个200分，估计HL一流选手的大众分应该在400以上，省一分数线可能大概290~320分（Flag 2），想拿到一个对省选有利的分数还是不大容易的。 等了一会，等到了igronemyk神仙，神仙听了我D1T2的做法觉得我很神。又和Cris、partychicken预测了一下今天三道题的内容（禁赛警告），T1模拟，T2较难的DP，T3九条可怜（具体内容为斗地主的某种排列），应该不会有图论了，毕竟昨天我已经写了两道图论题了（我知道你们T2写的都是完全背包行了吧）。（Flag 3 8:05入场，发矿泉水，发草纸。 8:30准时开考，密码：笑书神侠（才发现两天的密码都是纪念金庸） 一遍输对密码，解压，打开题面： T1图论。。。T2什么鬼？T3图论，有44分的暴力分 #### T1 先看看T1。n个点m条边，无向图（哇，是不是双连通分量缩点，我刚复习这个），无重边，无自环，DFS形成序列的字典序最小。 蛤？这和昨天的原题大战完全不是一个画风啊！ 看看数据范围：n的范围，$O(n^2)$可过。m的范围， 出题人你怎么不早说这是个环套树？枚举环上被ban掉的边，贪心+dfs就行了啊！ 9:20切掉T1。 #### T2 T2的数据范围看起来很像是个状压DP，算算复杂度，猜测应该是$O((2^n)^3\log m)$的矩阵快速幂，卡常数。脑补了一个转移，先写了一发不带矩阵的试一试，第一个样例过了，第二个样例大一些，第三个样例大得多。调了半天没挑出哪里写错了。已经10:30了，时间浪费得有点多。emmm，先做T3 #### T3 T3的44分是经典问题，20分钟敲完。似乎还有一些零碎的分数但是不想打了。显然可以用动态DP做，但是我不会，还有个不成熟的虚树的想法，但是自己之前从来没写过虚树，不敢轻易下手。现在144分到手，算上昨天的（假装）有399分，要是切掉T2，应该就稳了。那就肛T2！肯定是状压DP（雾 #### 回到T2 大概一直debug+手算到11:30，发现自己的转移简直就是扯淡，完全没有考虑两路径相交的递推，可能只有```n=2```的时候是正确的。只有半个小时了，决定用自己错误的代码处理大数据（除了第一档之外都是大数据），手算第一档的20分。 然而自己已经慌得一批，根本算不进去。心里只想着自己T2崩盘了，要退役了，滚回去学文化课了，没有大学要我了。。。 30分钟飞快地过完了。检查完文件读写，回想三个半小时之前，我为什么会觉得T2是个状压DP？又为什么没有在一开始就Hack掉错误的想法？明明可以随手打个50分的暴力，再去打T3的零碎暴力分。其实我T3的代码稍加改动就可以再过掉两个B1的数据（B1只需向上暴力合并答案），这样我至少能拿到202分的高分。可是，没有后悔的机会了。根据往年HL菜鸡互啄的形势，估计今年HL的最高分应该是100+100+100+100+50+44=494分，400分左右的应该会很多，分数会很密集。菜是原罪，考炸大概还是因为我菜吧。 #### 考后 等着收代码的时候去了趟卫生间，partychicken说他突然发现他T1的序列是用```std::string```存的，只有$n\leq100$的时候能得分。partychicken考前的时候说，只要今年他还是省二，就可以在机房颓到高三了。但是崩了这一道题似乎并不影响省一。 然后Cris和igronemyk就在讨论T2里$n=3$时的公式。顿时感觉这两位明年进队稳了。 回到座位上，牡丹江一中的神仙问我T1咋做，我说这不是环套树傻逼题吗，他又吓傻了。。。 回到家里看了一下昨天普及组的题，感觉比去年的普及组要简单一些，除了T3比较烦之外还是比较水的，尤其是T4，可以说是近年来最水的T4。 ### Day 3 从0开始的文化课生活。 第一堂是语文课，全班齐诵《梦游天姥吟留别》，当时就懵逼了，期中考试卷这么快就讲完了吗。第二堂地理课，完全听不进去，心里想的都是赶快发代码。第三堂数学，排列组合习题（好水啊）。第四堂嘤语，阅读6+1已经留到了73页，我刚做到49页。。。第五堂物理，开磁场新课，听得还是比较轻松的。 中午吃完饭之后去机房，olit小姐姐说D2T3是水题，只要处理处每个节点的up和down，倍增就行了。这个真的是正解，比动态DP或者是虚树好写得多。可惜的是她没时间写了，只打了44分暴力。VCode说自己只打了406分的代码，D2T3写的是$O(2^n)$的低级暴力。。。高一的都很惨，毕竟今年题目画风比较奇怪，比较考验人生经验，估计是几乎没有高一拿省一的了。 老张说下午发代码。打算晚课之后吃完饭来洛谷自测一发。 第六堂体育课，打羽毛球放松一下紧张的心情。第七堂生物，妈耶，春哥讲得太快了吧，已经讲到5-3了，赶紧借同桌笔记抄一下。第八堂地理加课，继续复习必修一。第九堂和晚课是数学，讲了两道解析大题作业，一堆排列组合杂题。 吃完晚饭之后，突然想起来现在学校有新政策，6:00~7:00实验楼封楼。只能放学回家后测了。 晚自习也不在状态，心里全是NOIP，就只写了明天要收的作业，补了十几页嘤语阅读+完型。 回到家第一件事就是开电脑。老张已经把代码传到群里了。HL-0131，赶快测一发！ D1T1。。。100 D1T2。。。70？心里凉了半截，完了，退役预警。 D1T3。。。25？蛤？我打了55分啊？D1只有195分，真的退役了。 D2T1。。。100 D2T2。。。50 D2T3。。。44 少得可怜的389分，彻底凉了。昨天心里还有那么一点侥幸，总是告诉自己D1T2的算法的正确性是有保证的，时间复杂度还更优，但是D1T2和T3全挂了。D2T2要是一开始的方向就是正确的，还能多得15分，而且给T3的时间还更充裕，完全可以多拿一些暴力分，说不定还可以搓出虚树正解。 在OI队的水群里，我发了一句：凉了，389分，D1T2和T3全挂了。 然后VCode就回复：满dar佬的民间数据评测已经出来了。然后他发了一个xls。 我点开： qzh 高一 510 。。。不对啊，他不是高二吗？ 在屏幕的低端，我看见了我的名字。正睿数据的结果是384分，全省第19。 我的上面，是黑压压的一片“哈尔滨师范大学附属中学”，顿时眼前一黑：这次三中崩了！ 仔细数了一下，发现自己星际了，我前面的三中非高三选手有五个，师附的非高三选手也是五个。。。佳一有点惨，只有qzh和dmf分数比较高。德强的xtx的分数有些让人惊叹。想了想，自己想省选翻盘，就要比graygoods高50分。。。对于我这个今年省选场外240分的菜鸡来说真的不大现实。况且CCF的数据一般会比正睿和洛谷要略强，可能我D2T2连70分都得不到。 唉，想这些又有什么用呢？技不如人，告辞了，OI。梦该醒了，学文化课去了。 不负责任地预测一下明年省队分布：哈三中3+师附4+佳一2+德强1+齐实验1（如果省队11人）。可能会有两个妹子进省队。 ### Day 10 100+35+30+100+50+44