NOIP2018游记

\(Day0\)：
今天应该是要看考场的。
早上没有训练。在机房趴着睡到了九点多。然后起来划水到了十一点多。
中午吃完饭回来在机房和两个同学一起刷知乎，然后补番到一半又开始复习数论。接着看到了一道“好”题，就和同学一起口胡了一下。
然后上去试机，开始打之前看到的那道题，但是没打完试机就结束了。然后下楼以后继续开心debug，但是还是没有弄出来。回到宿舍以后继续开心debug，终于调出来了。真是一道丧题。
对，我说的就是NOI2004 郁闷的出纳员。
（话说调到一半调不下去了，看了一集「黄金拼图」，然后回来就调出来了，愿吉老师赐予我力量（大雾））

\(Day1\)：
T1大水题，T2有点小坑，以为是数论结果写了正解思路自己以为是暴力，T3给了很多部分分然后拿部分分的时候想到正解来不及打（也打不出来）。
感觉这场有点水，大家都考得很高，我估分好像也比较高，我觉得有点方。主场作战也是有优势的，上厕所调整思路真是超有用的。
大概就是这样。
今天并没有见到某个喜欢做很多事情的女孩子，希望明天也不要见到。（大雾）
话说打开空间才发现明天竟然是双十一。虽然在广告中有看到但是好像没有实感的样子。

\(Day2\)：
令人欣慰的是，今年真的没有那位女孩子。而且本人在群里说了并没有参与出题，太爽了。
今天的题比昨天不知道丧到哪里去了。传说今年的题存在一个叫做时间-难度不等式的东西，居然是真的——
$$ D_{1}T_{1}<D_{1}T_{2}<D_{1}T_{3}<D_{2}T_{1}<D_{2}T_{2}<D_{2}T_{3} $$
试卷的解压密码是「笑书神侠」，仔细想想昨天的解压密码是「飞雪连天」。莫名间一阵伤感。
T1和我出过的某一道题非常神似，都是在求一些特定的\(DFS\)序。就连对\(DFS\)的描述也和我的描述非常相似。
所以在考场上我用了几分钟的时间概括出了简要题面，然后用了十分钟写掉了。
T2和T3简直丧心病狂。
T2我一开始以为是一道结da论biao题，然后就写了个暴力硬上。打了一张5*6的表格，然后找规律推了\(65\)分的公式出来；
很容易可以发现两个定理：
一：对于一个点，如果它的左下方是0，那么它就不可能是一。
二：对于一条左下-右上的斜线段，如果它的颜色一样，那么位于它右下方的所有斜线段颜色都必须一样。
那么我们就可以考虑\(DP\)，具体来说，就是，记每一条斜线的\(0-1\)分界，然后从左上往右下转移。
T3先是写了链的部分，一开始思路错了，是把序列拆成三个部分然后分别处理并且合并，写了一个三十多行的转移。然后上了一下厕所回来发现自己简直是智障，其实就是，把「要求放的地方的花费设0，不要求放的地方花费设无穷大」。然后其实就变成求带权树上覆盖集。这种做法的复杂度是\(O(n*m)\)的。如果足够聪明你就会发现，其实在求出初始花费之后，每一次询问造成的影响只会影响从这一个点到根的一整条链。所以找到树的重心之后用这种方法更新，可能可以缩小常数。
总之T2、T3我到现在都不会写正解。
考试剩下五分钟的时候感觉还不错，可能今天可以拿\(233\)分。结果测一下大样例发现我T3的暴力写挂了。所以就不知道会炸成什么样了。
出来以后在考场门口合了个影，然后就开始愉快划水了。
（尽管明天需要期中考qwq）
题目解析：
解析什么的…不存在的23333
祝大家RP++
NOIP2018 D1T1铺设道路
NOIP2018 D1T2货币系统
NOIP2018 D1T3赛道修建
NOIP2018 D2T1旅行