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(nlog n)),想了一会想到了分治,就随机 modify 一些点然后把亮的点和不亮的点分成两部分递归下去。

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

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

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

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

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

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

day3

  闭幕式。

  面麻真开心。

总结

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

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

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

  最后

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

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

  大家文化课&OI加油!

原文地址:https://www.cnblogs.com/ywwyww/p/11221991.html