NOIP 2018 退役记

## NOIP 2018 试题列表： $ \qquad $[D1T1 铺设道路](https://www.luogu.org/problemnew/show/P5019) $ \qquad $[D1T2 货币系统](https://www.luogu.org/problemnew/show/P5020) $ \qquad $[D1T3 赛道修建](https://www.luogu.org/problemnew/show/P5021) $ \qquad $[D2T1 旅行](https://www.luogu.org/problemnew/show/P5022) $ \qquad $[D2T2 填数游戏](https://www.luogu.org/problemnew/show/P5023) $ \qquad $[D2T3 保卫王国](https://www.luogu.org/problemnew/show/P5024) --- 一年OI一场空... 这是我第一次参加NOIP，也是最后一次参加NOIP了 在退役之前写最后一篇文章纪念一下 --- # 2017.07 - 2017.10 中考完后的暑假，不是在家和朋友语音开黑聊天打游戏，就是出门浪~~(颓废)~~。闲来无事，突然心血来潮想要学习C语言，在B站找到了[翁恺的C语言微课](https://m.bilibili.com/video/av6001731.html)开始学敲代码(130多集的微课我居然三个月就看完了)，我的OI生涯从这里开始. --- # 2017.11 - 2018.11 ### $ \qquad $2017.11.04 $ \qquad \qquad $加入Luogu ### $ \qquad $2017.11.05 $ \qquad \qquad $成为了小小牛 ### $ \qquad $2017.11.08 $ \qquad \qquad $成为了小小犇 ### $ \qquad $2017.11.22 $ \qquad \qquad $成为了小牛 ### $ \qquad $2017.12.24 $ \qquad \qquad $成为了小犇 ### $ \qquad $2018.01.13 $ \qquad \qquad $成为了中牛 ### $ \qquad $2018.02.05 $ \qquad \qquad $成为了中犇 ### $ \qquad $2018.02.25 $ \qquad \qquad $成为了大牛 ### $ \qquad $2018.03.15 $ \qquad \qquad $AC[树链剖分模板](https://www.luogu.org/record/show?rid=6222115)——我人生中AC的第一道紫题啊！！！ ### $ \qquad $2018.03.28 $ \qquad \qquad $第一次独立AC蓝题 ### $ \qquad $2018.03.30 $ \qquad \qquad $成为了大犇 ### $ \qquad $2018.05.04 $ \qquad \qquad $AC 100题(大概有90%是黄题及以下吧Orz) ### $ \qquad $2018.05.12 $ \qquad \qquad $成为了神牛 ### $ \qquad $2018.06.23 $ \qquad \qquad $AC 200题 ### $ \qquad $~~2018.08.02~~ $ \qquad \qquad $~~成为了神犇(fAKe)~~ ### $ \qquad $2018.10.11 $ \qquad \qquad $AC 300题 ## 特别感谢[Villard](https://www.luogu.org/space/show?uid=27573)(尽管如今他已经退役了): 初中三年每年都看着他参加NOIP，以前闲聊时他也常常给我普及一些算法知识(尽管当时的我不怎么听得懂)。在我入坑OI后他不仅经常手把手教我调试Luogu新手村的水题(在当时的我看来都是神题)，还在第一时间教会了我怎么写dfs、bfs、求最长上升子序列 LIS，以及用 Floyd/Dijkstra/SPFA 求单源最短路，这在当时(2017.12)算是领先了与我同时期入坑OI的大多数人(尽管现在我已经远远落后于各路神犇)，为我之后学习各种算法奠定了坚实基础。 --- # Day-1 & Day0 ## 2018.11.08 - 2018.11.09 考前两天已经不怎么写新题了，就打了几个模板，再从[P1000 超级玛丽游戏](https://www.luogu.org/problemnew/show/P1000)开始看看这一年写过的题. 学机房dalao打了一颗[完美线段树](https://www.luogu.org/paste/evgtymjh)，不知道考场上用不用得上. --- # Day1 ## 2018.11.10 毕竟我是第一次考NOIP，虽然模拟赛已经打了不少了，但是真正上考场还是比较虚的，并没有十足的把握拿省一. ## 8:30 拿到题目之后看的第一眼，三道题名暗示了图论?(road), 数论?(money)，数据结构神题?(track)，不过看了一眼内存空间限制512MB，感觉应该比某些毒瘤卡空间模拟赛轻松一些. ## 8:32 看完T1题面的第一反应：woc，这不是[NOIP 2013 D1T1 积木大赛](https://www.luogu.org/problemnew/show/P1969)？我没有读错题吧，是不是有坑？然而5分钟敲完的积木大赛的代码，小样例大样例都能直接过掉，应该没什么问题. 100pts到手了. 炒冷饭，就服CCF，hhh...... ## 8:40 读懂T2题面后的感觉是：这难道是小凯的疑惑毒瘤增强版？那遇到纯数论题就只能打暴力的我岂不是凉了？再看一眼数据范围 $n \leq 100$, $a_i \leq 25000$，没达到$10^{18}$那么吓人，感觉暴力或者乱搞还是勉强能拿部分分的. 在草稿纸上乱搞了10分钟后发现答案应该是给出的那一堆货币面额的子集，否则会不符合题意，那么似乎可以$O(n^3)$枚举每三个数，看看较小的那两个数能不能凑出较大的那个数，如果可以就去掉. 诶？这是不是小凯的疑惑？又花了十几分钟打出一个 $O(T * n ^ 3)$ 的做法，过了样例1，但是样例2没过——第七组和第九组数据WA了，输出居然比答案多1. 赶紧debug看看是哪一个数字没有被fuck掉，发现一个数如果能被另外三个或以上的数乘上系数凑出来也是可以合法被去掉的——woc这真是小凯的疑惑毒瘤增强版. 冷静一下，我开始认真思考这题要怎么搞，想起有道dp题叫[砝码称重](https://www.luogu.org/problemnew/show/P2347)，把数从小到大排序，赋初值$ans=n$，开个$bool$数组记录一下每个数可不可以被前面的数凑出来，如果可以(被标记过)就令$ans-1$，否则遍历该$bool$数组并把"这个数的倍数+已标记的$bool$数组下标"标记上。把这个做法敲出来，调一调就过样例2了，期望如果数据友好一些就可以AC了. YES!!! ## 10:35 写T2之前就瞥了一眼T3，感觉题目太长就没细看，觉得T3敲个暴力就差不多了，毕竟T3通常不可做. 现在仔细读题：要求最小值最大？明显要二分. 再看第一档部分分：$m=1$？也就是说求个树的直径就可以拿20. 赶紧敲了个$Dijkstra$+$Heap$优化的最短路（因为写的比较熟）. 再看看剩下的部分分，菊花图和一条链的数据好像可做，菊花图搞个 二分+排序+贪心 应该就可以了， 一条链也是 二分+贪心， 又搞了40分钟，生成了几组小数据拍过了，感觉可以拿55了，剩下的分看起来是树形dp，但是懒得想了（主要是我太菜了想不出来，而且也没时间了），所以写到这里就差不多可以交了. ## 12:00 检查完文件名和输入输出就交了. DAY1 考场部分到此结束，刚出考场时期望得分还是有255的. ## 15:30 一觉醒来准备想去机房颓废，突然想起：早上T2如果造出前99个质数+一个25000的数据那我岂不是TLE飞去？因为这时候复杂度最坏可以达到$O(T * n * ({max\{a_i\}})^2)$. 这么算来T2只有75分是稳的了，希望数据友好一些吧...... 还有T3，突然想起来我二分答案的范围好像设错了，原题中是 $l_i \leq 10000$ 来着，而我为了调样例方便把上界设为 $r=30000$ ，提交前忘记改回来了，并且在一条链的数据中忘记将边的长度序列从小到大排序，如果数据中$m$比较小或者输入的树边不是按顺序的那就gg了. 菊花图和链的30分又没了，唉...... D1期望得分掉回225-了. --- # Day2 ## 2018.11.11 由于D1T1出了NOIP2013原题，导致Day1整体偏简单(大概全机房除了我，都AK了吧).所以早有传闻Day2的题会爆难(同机房dalao多次警告：可能会有传说中毁天灭地的第七分块，建议直接打暴力...Orz). ## 8:30 由于早就听说Day2的题不太可做，于是开考后我先干点别的，比如先验证一下昨天机房dalao所说的今年CCF评测机换成 Intel® Core™ i7-8700K Processor + 32GB RAM 了，一看注意事项还真是如此，Day1考试的时候没注意这一点，没想到第一次参加NOIP就碰上CCF老爷机换成CCF队爷机了，这就意味着代码常数大一点也没事，但是不知道是用什么主板，而且Noi Linux万年32位的系统又怎么寻址得了32GB？~~不过如果CPU上个液态氮，超频到8.0GHz，那么写个暴力大搜索也是能过的吧~~. ## 8:33 颓废结束. 先把3题都看了一眼，感觉T2 T3题目又臭又长又不可做呢. ## 8:35 跳回来认真看T1.依照题意，要求一张图的字典序最小的dfs续，看起来直接从1号节点开始贪心dfs可做，不过第一眼看错题目了，以为是一张普通无向图，想了5分钟想不出一些边界条件的处理方法，然后才发现有 $m \leq n$ 这个条件. 那么前60分$m = n - 1$的数据就稳了，几分钟写个dfs，然后先用邻接矩阵村边，再从大到小遍历邻接矩阵，改成链式前向星存边，这样就可以保证严格按照最小字典序进行dfs遍历，而且是跑得超快的 $O(2n-1)$ 时间复杂度的dfs. 重点是后40分 $n = m$ 的情况，咋一看直接照着前60分的方法dfs一次，遇到走过的点就退出就可以了，结果样例都过不了. 然后开始想各种奇怪的dfs方法，什么“记录每个节点的次小子节点并与当前节点比较来决定是否回溯”、“记录每个节点前驱最小子节点并与当前节点编号比较来决定是否回溯”、“动态判断子节点能否被再次搜索到来决定是否回溯”之类的玄学方法，但是都过不了样例. 此时已经9:15了，如果再写不出T1，Day2就凉了...... 突然想起来我们不是要处理环嘛，若要很方便地处理环套树，那自然是用Tarjan求双联通分量，然后只要记录一下首次搜索到环的入口节点的次小环上子节点，一旦搜索到编号比该节点大的环上节点就立即回溯，这样应该就是最优解了. 花10分钟写了个Tarjan，结果写挂了，调了20分钟才救回来. 测一下样例，诶？居然大小样例都能过，那这题就AC了？(事实上这样做是错的，Day2当天晚上同机房大佬[srydsf123](https://www.luogu.org/space/show?uid=96312)在听了我的解法后瞬间出了一组数据Hack掉了这种做法，这说明大样例还是挺水的). ## 10:00 T1已经困了我一个半小时了，T2 T3打打暴力应该就差不多了，毕竟Day2对于我这种蒟蒻来说有个100+就不错了. 看见T2，读了差不多10分钟才知道题目想干嘛. 感觉要做出来得打表找规律，那就先打暴力. 但是这个暴力还是不太好打的，得先枚举出所有路径，再枚举01矩阵并检验是否合法. 打了20分钟的暴力，测测样例1：Yes!!! 过了；测测样例2：woc!!! 输出96？什么鬼，我暴力写挂了？然而20分钟肉眼调试并没有查出错误...... (为什么CCF不把样例2解释一下啊，112种可能结果很难一一列举出来么#滑稽). 没辙，已经快11:00了，万一T3暴力又写挂今天就真的凉了，于是T2我放上写挂的搜索+输出所有样例就走了. 至于这题有没有样例分就只能拼rp了. ## 10:55 T3题意蛮容易读的，可能正因为这样，我竟然读错题了，我以为这题就是[保安站岗](https://www.luogu.org/problemnew/show/P2458). 先10分钟打出 $O(m * 2^n)$ 的大暴力，测一测小样例，可以过。然后因为不太记得保安站岗的详细做法，所以决定先不写保安站岗的树形dp了，转而去写一条链的部分分. 又是20分钟过去了. 已经11:30了， 因为没有一条链的样例，所以这个做法对不对只能听天由命了. 然后突然发现样例2的数据规模挺小的 $n,m \leq 10$， 就拿来测一下 $O(m * 2^n)$ 的大暴力——竟然WA了？还剩半个小时突然发现T3面临爆零...赶紧肉眼静态查错(在我这种蒟蒻眼中debug暴力程序的方法就只有这种了吧). 一查又是20分钟，找不出任何bug，样例2死活过不去，但只能这样了. ## 11:50 检查文件输入输出就准备交了吧，T1算法的正确性仍有待验证，T2 T3很可能爆零，Day2估计是凉了. ## 12:00 刚出考场就突然想到，woc T1直接$O(n^2)$枚举删掉哪一条边然后再dfs不就可以了？我在考场上居然没想出来...... ## 21:20 机房大佬[srydsf123](https://www.luogu.org/space/show?uid=96312)Hack掉了我T1的后40分做法，至此，Day2期望得分只有60-80分了 --- 期望最高得分($Day$ $Dream$ - Orz): 100 + 100 + 55 + 100 + 5 + 0 = 360 期望最低得分： 100 + 80 + 20 + 60 + 0 + 0 = 260 用[Luogu](https://www.luogu.org/contestnew/show/12952)提供的数据测试得分: 100 + 95 + 55 + 72 + 5 + 0 = 327 用机房大佬[Dystractor](https://www.luogu.org/space/show?uid=117525)提供的数据测试得分: 100 + 100 + 25 + 76 + 5 + 0 = 306 用友邦提供的数据测试得分(运行结果由[laybxc](https://www.luogu.org/space/show?uid=51441)传达): $\overline{???}$ + $\overline{???}$ $\Big( \overline{??} \Big)$ + $\overline{??}$ + $\overline{??}$ + $\overline{?}$ + $\overline{?}$ = 309 CCF生成测试数据得分(Reality)： 100 + 100 + 35 + 68 + 10 + 0 = 313 ```cpp /* * ┏┛ ┻━━━━━┛ ┻┓ * ┃　　　　　　 ┃ * ┃　　　━　　　┃ * ┃　┳┛　 ┗┳　┃ * ┃　　　　　　 ┃ * ┃　　　┻　　　┃ * ┃　　　　　　 ┃ * ┗━┓　　　┏━━━┛ * ┃　　　┃ 神兽保佑 * ┃　　　┃ 代码无BUG！ * ┃　　　┗━━━━━━━━━┓ * ┃　　　　　　　 ┣┓ * ┃　　　　 ┏┛ * ┗━┓ ┓ ┏━━━┳ ┓ ┏━┛ * ┃ ┫ ┫ ┃ ┫ ┫ * ┗━┻━┛ ┗━┻━┛ */ ``` --- 个人认为今年NOIP画风是真的鬼畜(贪心运气好就AC，运气不好则爆零；猜结论猜对者AC，猜错者爆零)，D1T1出2013年原题实在欠妥，这不仅让GX-TG组的省一分数线提高数十分之多，而且对没写过此题的选手不公平(友邦朋友验证). 另外，这次NOIP竟然没有考数据结构题(不考线段树、树状数组~~、BST、Treap普通平衡树~~之类的就算了，连个栈、队列、链表都不考么，这堆数据结构学了然并卵诶). NOIP 2018在GX-TG组的省一分数线目前尚不明确(机房大佬们预测省一线在250分左右). 虽然有消息称我的分数是稳省一的，但是由于我在这次比赛中过多使用玄学算法，因此我最终的得分与排名仍有很大的不确定性. 对我个人而言，Day2考的太差，因为看错、写挂而丢了很多分，早知如此就应该死磕D2T1，不打T2 T3了. 有人告诉我说我搞一年OI就可以得省一其实挺值的，但在我看来，这次NOIP终究是有挺多遗憾的...... --- 最后在此感谢所有帮助过我或与我共同奋斗过的人: $ \qquad -$[Uchiha_Obito](https://www.luogu.org/space/show?uid=31470)/[Dystractor](https://www.luogu.org/space/show?uid=117525) $ \qquad -$[GoldenPotato](https://www.luogu.org/space/show?uid=52563) $ \qquad -$[li_z](https://www.luogu.org/space/show?uid=60418) $ \qquad -$[Villard](https://www.luogu.org/space/show?uid=27573) $ \qquad -$[Ace_Heart](https://www.luogu.org/space/show?uid=81494) $ \qquad -$[Maxwei_wzj](https://www.luogu.org/space/show?uid=13447) $ \qquad -$[114514_hb](https://www.luogu.org/space/show?uid=83224) $ \qquad -$[srydsf123](https://www.luogu.org/space/show?uid=96312) $ \qquad -$[Capacitance_core](https://www.luogu.org/space/show?uid=58595) $ \qquad -$[迅捷之松](https://www.luogu.org/space/show?uid=77262) $ \qquad -$[Summer_Night_Sky](https://www.luogu.org/space/show?uid=64314) $ \qquad -$[Glodfish](https://www.luogu.org/space/show?uid=81746) $ \qquad -$[laybxc](https://www.luogu.org/space/show?uid=51441) $ \qquad -$[zhlgzhh](https://www.luogu.org/space/show?uid=82001) $ \qquad -$[Seass](https://www.luogu.org/space/show?uid=83709) $ \qquad -$[SHDZAYN](https://www.luogu.org/space/show?uid=90249) $ \qquad -$[LSYZX](https://www.luogu.org/space/show?uid=85126) $ \qquad -$[502Chain](https://www.luogu.org/space/show?uid=81747) $ \qquad -$[泅荼](https://www.luogu.org/space/show?uid=41950) $ \qquad -$[nnezhb](https://www.luogu.org/space/show?uid=43068) $ \qquad -$[nnez_xiaoliwei](https://www.luogu.org/space/show?uid=28416) $ \qquad -$[hebomou](https://www.luogu.org/space/show?uid=9661) $ \qquad -$[o0数学迷0o](https://www.luogu.org/space/show?uid=4025) $ \qquad -$[[用户名敏感问题待定]](https://www.luogu.org/space/show?uid=116425) (stO %%% zxbtql %%% --☐-☐-- %%% Orz) $ \qquad -$[Mireco](https://www.luogu.org/space/show?uid=116588) $ \qquad -$[5743377_2002](https://www.luogu.org/space/show?uid=36701) $ \qquad -$[ComputerEngine](https://www.luogu.org/space/show?uid=65899) $ \qquad -$[Zarathustra](https://www.luogu.org/space/show?uid=73738) $ \qquad -$[dmidcoder](https://www.luogu.org/space/show?uid=86680) $ \qquad -$[AMDYES](https://www.luogu.org/space/show?uid=81724) $ \qquad -$[nnezhhh](https://www.luogu.org/space/show?uid=85734) $ \qquad -$所有值得感谢但因为各种原因未在该列表中出现的人  祝各位NOIP 2018 RP++. --- By [Von Brank](https://www.luogu.org/space/show?uid=70367) Last Updated at 2018-11-20 08:23:49