Noip2017 滚粗记

我拥有何物？ 如此询问道
仅仅只有白纸一张
那大概是
为了以自己的画笔描画而准备的
最初的一页

抬头所见的青空 鲜艳地映入眼帘
如果可以的话好想就这样
试着让这颜色 将自己涂染

在那无尽延伸的天空彼方
等待着吗 我所探寻之物
比昨天再向前迈出一小步
现在，伸出手来吧

—— Hatsune Miku

Day -2

（别人在半期考试）
连续几次考模拟赛的成绩不是特别理想，讲完正解又觉得自己好傻，为什么这么简单的题我就是不会做呢（我是怎么考进来的）？直到晚上才想起来应该把去年的题过一遍……
然而发现去年的题对我来说太难了，连组合数都没有想到用二维数组存储答案，玩具迷题都搞不出正解:(

Day -1

（别人还在半期考试）
最后一次模拟赛，结果还是靠第三题水了100分

T3题目大意：输出你期望的noip分数

读完题目挺感动的（是指的出题人的独白），当时我好像是胡乱输出300（雾）
下午和晚上又去刷去年的题，天天爱跑步居然水了80分，十分开心。

Day 0

（别人仍在半期考试）
教练说今天上午可以不去学校，我本来七点钟被叫醒，在和母上大人一番和平友好（死皮赖脸）的交涉后，我又回去睡到了……也许是十点吧。
中午吃了金拱门就赶到学校去，赶上教练发准考证和宣读壮士出征前最后的提醒（当然还是那些常用的套话啦，什么开文件啊，放在哪个哪个文件夹下啊，不要走错校区啊，这些我们都知道）。
散会后，跑到隔壁机房去熟悉了一遍虚拟机Linux下的编译，没有想象中的那样困难。
然后把半期考试网上阅卷的流程熟悉了一遍。
下午回家倒头又睡，母上大人催了好久才起来，然后她驾车约莫一个多小时，终于到达了电子科大旁边的酒店。
教练说最近几天要吃清淡一点，于是晚上吃了烤鱼（挺香的）。
晚上又开一次会，教练强调了a.要搞清楚自己的知识水平，区分自己哪些题有把握，哪些题只能上暴力; b.考前先通读题，仔细分析不出来; c.不要贪; d.不要让Day1影响Day2; e.才高一，体验考试。（对我这种蒟蒻来说很有道理）
很早就睡了，但是由于生物钟，还是清醒了好一阵子才睡着。

Day 1

日常七点起床（酒店餐厅十分小，早餐十分难吃）。
八点多进了考场，把身份证放在准考证上，准考证放在右上角。后来寻思着监考老师要检查证件，于是欲将其转到左边。直接去提准考证，然后身份证直接掉进了桌子缝中（桌子推不开的，我试过）。当然监考老师是很和蔼的，而且答应下午帮我取出来。
八点半领了题包，太兴奋、太激动害得我输错了三次密码。

Day1 正文

T1在某本书上看到过结论，5min结束（想着在考试，就没有尝试去证明）。绝对100分。

T2一看就知道是大模拟。先把输入给处理了，我全文是用的getchar()读入，由于有很多的空格和换行，所以在读入这里处理了很久很久（三四十分钟）。输入搞完过后开始想for循环的各种情况（感谢样例提供了两种我没有想到的情况）。然后后面就很简单了，各种情况全部判过去。然后我又发现我不能在中途直接输出ERR然后continue，因为这样会影响后面的读入，于是开了个布尔值来判断是否输出ERR。后来在大样例发现有可能E比F少的情况，赶紧加上去。然后还是死活过不了大样例，打了一大堆调试语句才发现当x或y为n时我会把它赋值为-1，结果造成n反而比常数小的尴尬局面。看到大样例过了，我也就放心了。期望100分。

T3看上去有点难办了（对我来说）。先跑一遍SPFA把最短路找出来，存储每一个点到起点的最小距离（far数组）。然后DFS，如果当前距离比(far[当前节点]+k)还要大一些，就return（理论上可以剪一大堆枝）。每一次到达终点就ans++（不能return)。期望30~50分吧。

Day 2

非正常七点起床（周日习惯了九点起床）。
监考老师把身份证还给了我（好开心w）。
八点半领了题包，今天很沉着，只输错了两次密码。

Day2 正文

T1在雅礼时做过一道类似的题，不过那个是二维的（没毛病）。直接两两枚举所有点看能不能互相联通，能联通的就连一条双向边（两条单向边），最后从上往下跑一边BFS即可。但是却忘开long long（哭给你看）。期望80分。

T2貌似有点复杂了。看到n的数据范围那么小，于是就想到了状压DP，但是并不知道怎么转移……然后便开始了枚举之路。我是枚举以每一个点为起点的最小花费，先将每一个点的权值（权值表示从其周围已经连接到起点的点到达这个点的最小花费）赋为超级大。使用BFS（我是不是BFS用太多了?），每一次看能不能更新权值，能更新就更新。小样例随便过，大样例输出300多（十分慌张）。接下来发现原来有可能儿子更新父亲，这是很不妙的，加了个判断上去。紧接着大样例输出440，我查看了大半天没有发现毛病（特别慌张），看到时间还剩一小时多的时候，马上去撸T3。

T3恐怕已经不是我能理解的了（夸张）。发现对于大部分数据，整张表是没法储存下来的，然后各种想怎么存（树状数组?线段树?平衡树?），反正想不出来。于是只打了暴力（n<=1000&&m<=1000的情况和n==1的情况）。期望30分也知足了。

回来继续T2，最后终于发现了自己的问题：一个点的深度是父亲的深度+1，可能在前面父亲的深度很小（但是权值很大），于是乎这个点的权值也就被钦定了。接着后来父亲的深度变大了（但是权值反而减小了），这个点的权值却不会再改变……这就是为什么比正确答案小。此时只剩下一刻钟了，胡乱调试，也没管输出了447，就匆忙结束了比赛。奇怪的搜索期望30分。

Day 3

回到教室，认识同学。
装作听得懂然而并听不懂老师讲的什么。

Result

期望370分，不容乐观