NOIP2018爆零记。

Day 0

由于今年我们学校是主办方，所以就没法住宾馆，只能住寝室。(不能随意颓废了。。。)

然而考前颓废有助于发挥是常识，于是我就冒着被查表的风险开始在机房放飞自我了。

晚上看了几集番，刷了会知乎(看各路神仙对NOIP的毒奶)，由于要求提前回去睡觉，于是在8:30就回寝室睡觉了。

Day1

早上由于要出发去紫金港，所以6:30就起床了。然后就带上了自己的电脑，在车上看了几集番。

到了紫金港，和同学奶了几波NOIP的题(和贺指导)就进考场了。

然后开题。

看到€€£换了评测机很开心，觉得不会卡常了。

先看T1，一开始想每次贪心减整个序列，最小值减成0后再分治下去。想一想发现这个做法要建笛卡尔树，显然不是T1难度。然后想倒过来从大到小枚举来做上面的过程，相等的段可以用并查集维护。然后觉得这好像也不是T1难度。最后思考了一下，发现自己sb了，这题似乎和前天的NOIP模拟题T1似乎一模一样，瞎贪心一波就好了。然后随便写写就写完了。

然后看T2，看完之后先大力猜一波结论，感觉如果一个数可以被其他数表示出来就把它删掉就好了。然后随便证明了一下(大概就是最小值肯定得选，然后次小值如果不能被最小值表示出来也就肯定得选，以此类推)。然后就是个无脑背包了。

最后开了T3，做好了题目很♂dark♂的准备。看完题后，显然得二分答案。二分完之后题目变成了最多能选多少条长度$\geqslant v$的边不相交的链。首先必须得先最大化每个子树内的路径数，在最大化路径数的前提下需要最大化从子树的根向下的最长的没有边被选的链。然后这个东西怎么转移呢，我们要做的就是拼接两个子树的向下的链。如果只是要求最大化路径数就直接sort一下然后从大到小用two pointers贪心一下，如果还要求剩下的向下的链尽可能长，我们就二分一下哪条剩下，然后直接再用前面的贪心check一下看答案会不会变就行了。

由于这次T3出乎意料的简单，导致我三道题写完后10:00都没到，于是就开始颓emacs的小隔膜到比赛结束。。。

出考场后发现大部分人都ak了，感觉难题都被放Day2了。

默写了考场代码后测了测洛谷数据，发现都过了。然后发现T1是NOIP2013原题，数据范围都没改。(€€£: 我抄我自己)

Day2爆炸预定。。。

Day2

咕了一个星期的Day2游记。。。

开场看题，先看了看T1，很快写完了，然后开T2。

看到T2这么长的题面，突然有一种不好的预感，然后看到了数据范围$n \leqslant 8$，感觉这是一道状压题。

做了一会儿，发现矩阵合法的条件:

  1. 一个数不能小于它右上角的数。

  2. 如果一个数和它右上角的数相等，那么它右边的格子到终点的所以路径都必须相同。

然后我觉得这个东西太复杂了，一定有更优美的性质(最后好像并没有)，然后就准备打个暴力看一下矩阵的性质。

打了暴力没有发现什么性质，然而发现了在$n > 1$，$m$很大时答案都是乘$3$，然后发现我的暴力只能跑$5 \times 5$。看了看发现$n \leqslant 3$有$65$分，然后就不管了。

然后还剩两个小时，看T3，发现没啥思维难度，是道码农题。由于我以为其他人都会T2，我觉得我只能靠T3拉回局面，然后就硬着头皮写T3的满分做法了。还好在比赛结束前拍上了，然后就不管了。

出考场后发现没多少人会T2，暂时松了一口气。

感觉把一年的RP都用在NOIP上了。。。