NOIP2018游记

# 赛前 “要不过一遍数论模板吧。” 已经晚上九点了，我却仍抱着那本信息学奥赛一本通苦读，希望找到一点点自己以前没有注意到的地方，好赶快补救一下。 这是NOIP的前一个夜晚。我的复习计划已经接近了尾声。前面的DP部分和数据结构部分都已经复习了三五遍，现在只有数论，这一毒瘤的大块没有复习了。 我本以为NOIP要求的数论知识我已经覆盖的差不多了，没想到一个叫做BSGS的东西却让我出了一身冷汗。“要是NOIP考这个，我岂不是完蛋！”我心想。当然，还有lucas定理和中国剩余定理一类的奇怪东西，我也不怎么懂。反正就这样昏昏沉沉，看完了数论，又想起一个叫做斜率优化的东西我好像差不多忘了，又随便翻了翻，看了看例题，便睡觉了。 还刷了一遍刺客传奇，希望能涨涨RP。 # DAY 1 早早来到赛场，却被告知要开考后才能用电脑，不禁让我怀疑是不是我之前都打的是假的OI比赛。 好像是提前开考了，密码竟然是feixueliantian（中间有防破密字符），不禁让人感叹NOIP出密码的人真是别有用心。 翻开题目，看到第一题，觉得眼熟。往下看，越来越眼熟了。看到最后，不禁笑了出来：咦，NOIP怎么出原题了？真的，这不是某个叫做积木游戏还是啥的题目吗？记得**一年前**是用一种奇怪的方法做过的，但是题解好像很简单。往递推这边想了想，便想到了$O(n)$的解法，第一题也就过了。 看到第二题，开始觉得有些意思了。看完题，再看样例，觉得样例瞬间降低了这题的难度。很明显，这题只需要排去能被同组面额表示出来的前就行了。至于这样做法的正确性，我证明了一小会儿，但也很快做出来了。完全背包打完，下一题。 第三题一看，我便傻了眼。这好像是第一天的神题了吧。正解想了一会儿，以为是DP，又想不出来，于是开始水部分分。结果水了两个小时的部分分，只剩下不到一个小时了，想着水点分吧，于是打了一个奇怪的贪心，心想是错解，就随便打打吧，结果到最后也没有打出来。然后NOIPD1就这样结束了。 出来才知道自己最后一题的那个思路好像是正解！于是下午打了一会儿，在洛谷民间数据上AC了。 心想明天不能再这样，自己可能会做的题目考场上却做不出来了。 晚上又打了一遍刺客传奇，涨涨RP。 # DAY 2 不打算先调电脑了，于是比较晚来到赛场。 密码忘了，好像还是关于金庸的。 第一题，第一眼看完觉得很毒瘤，因为有**基环树**。莫非老师的预言成真了？第二天真的是哈哈哈场？后来想了想，其实基环树上的那条路径也一定是棵树，枚举删边就可以了。（不知道有没有小于$O(n^2)$的算法呢。本人觉得应该是有的，但没有去想）。 第二题，一看便觉得是道好题，但又很毒瘤，且一定是道数学题，于是暂且跳过看T3了。 T3第一眼我以为是封锁阳光大学（哈哈哈哈哈……），吓得我脸色铁青，再看了看题目，方才知道原来相邻点可以都选。$O(n^2)$算法很明显，但其他部分好像不怎么好打，回去打T2。 T2开始找规律，$n=1$的时候规律显然，$n=2$的时候好像就不怎么明显了，于是打了个暴力看了看，发现好像$m$每增加$1$答案就乘$3$。再打了打$n=3$的，发现从第$4$项开始，规律也是乘$3$。$n=4$的时候也是。但是$m<=n$的时候却又不知道怎么打了。先打了$65$分部分分，然后想正解。 突然想到状压DP，存最后一列，相邻两列一定满足斜角大于等于的关系。满心欢喜打了上去，结果$3,3$的时候$144$输出错误，以为思路出错，便放弃了，去看T3。 T3打完44分，想再水点部分分。A的不会拿，看到B1觉得好打。打完之后验证，却一时脑抽了，以为变成了消防局覆盖问题，搞了差不多20分钟，等到最后只有10分钟的时候才缓过神来。 回头检查，发现T2注释掉了freopen！！！吓出一身冷汗，赶紧打回去，翻来覆去检查了一通，确保没有freopen被注释掉。 打完比赛回家，再想T2时，发现考场上那个DP的思路其实不是完全错误的，只是忘考虑了路线交叉时的情况。想到存最上方交叉且路径相等的点，打完了DP，利用乘$3$的规律（现在都不会证……），在洛谷上AC了。 # AFTER NOIP 源代码出来了，用老师提供的数据跑才$448$。QAQ啊。D1T3才35，D2T3才48，感觉这次NOIP炸了。 **总结一下经验：先打完暴力，然后全身心地想正解，不放过任何一个思路，争取正解。正解若不可，便保证部分分全拿。** 祝大家AK NOIP，省选RP++！！！