NOI 2019 游记

day -1

　　去报了个到，顺便买了一大堆衣服。

　　感觉学校饭堂不太行。

day 0

　　上午是开幕式，。

　　下午是笔试，顺利获得 \(100\) 分。

day 1

　　先看题。

　　第一题看到 \(At^2+Bt+C\) 就知道是斜率优化了，花了一个小时写完了。

　　第二题那个操作很像笛卡尔树的某些东西，后面的部分就是分段维护多项式。复杂度大概是 \(O(n^4)\) 的。

　　第三题研究了一会搞出了几个假做法。

　　突然发现第二题用到的区间不会太多，搜了一下发现只有不到 \(4000\) 个，就去把前 \(50\) 分的暴力写了，还有几个直接插值的点。

　　分数大概是 \(100+60+28\)。

　　这个 t1 数据超级水，各种暴力甚至暴搜都可以拿高分或者过掉。也不知道出题人是怎么验的题的。。。

　　t3可以用模拟费用流做，可是场上我连费用流都没想出来。

　　听说Au线是 \(200\)，减 \(10\) 分是 \(190\)，问题不大。

day1.5

　　社会活动日。

　　半路车坏了，等车等了一个小时。。。

　　面麻真开心。

day2

　　t1一看就可以用 kdt 做，再看到数据范围只有 \(70000\)，就写了。

　　t2可以DP，看到后面 \(60\) 分没什么部分分和梯度，就没去想了。

　　t3是个披着交互题外衣的题答题。先把 \(O(n^2)\) 暴力写了，然后对着每个部分分想做法。

　　看到了题目中注明了交互库是 non-adaptive 的，和 WC 的不一样，感觉这么些暗（ming）示了标程是随机算法。

　　特殊性质 A 的操作次数是 \(O(n\log n)\)，想了一会想到了分治，就随机 modify 一些点然后把亮的点和不亮的点分成两部分递归下去。

　　B 的操作次数也是 \(O(n\log n)\) 的，发现可以整体二分。

　　C 一开始想随机 \(O(\sqrt n)\) 个点然后往两边扩，写了一下发现操作次数太多了。就改成了随机一些点，拿其他点在这些点中间找连的边（整体二分）。

　　调了调参（选的点的个数）测了一下直接跑过了大部分的点。

　　得分大概是 \(100+40+92\)

　　出来听说大家都会打表找规律，感觉我要凉了。

　　t3 正解果然是随机化。。。还（不严谨的）证明了复杂度。

day3

　　闭幕式。

　　面麻真开心。

总结

　　感觉今年的题还是挺棒的。

　　没有大数据结构题体验极棒。

　　这次应该是真的退役了，以后很可能不搞竞赛了，博客会随缘更新（大概率是游记）。

　　最后

　　祝贺所有取得了自己满意的成绩的选手。

　　感谢所有 OIer 这几年的陪伴以及带给我的快乐。

　　大家文化课&OI加油！

巴特西