NOI2020-完美的谢幕

【写在前面】

这次NOI对我来说算是完美到近乎梦幻的谢幕了吧

由于幸运女神的眷顾，在这场最终的比赛中，我的能力、经验都得到了最充分的发挥

在最高的水平下、在最优的策略中、在最好的状态里、在一场没有被针对的比赛中

我侥幸踩在了队线上，被推到了一个我的硬水平并达不到的高度上

说实话，挺惭愧

但既然已经如此，便记下来吧

祭这最后的命运

(这篇博客就不讲琐事了，说说一些想法和考试吧)

【考前分析】

一、自我分析

我的水平自估是正式选手中的80名上下，银牌基本上是不成问题，所以只考虑如何得到金牌

相对于“六边形战士”，我的技能点是点偏的：数学和套路题是我的弱点，贪心和乱搞拿分是我的强项

二、得分策略

根据经验，绝大多数选手都会因为或紧张或失误而不能够得到水平内的全部分数

于是得到PlanA：在没有被“戳中弱点”以及拿到全部水平内分数的情况下，只允许出现一点点小失误，这样能够卡在金牌线上

备用方案PlanB：已知出现了大失误或者判断出有一道“杀我的题”后，再用稳妥的比法就失去了金牌的可能，此时必须放手一搏，尝试在一道题上造成优势

三、考场策略

预设使用多年比赛经验总结后最有效的策略：

在拿到题以后先按照顺序看题，每题给自己最长30分钟的思考时间，超时后强迫自己停止

在1.5h时在草稿纸上写下每道题的期望得分以及拿到这些分需要的时间

接下来判断这些分是否达到了大多数人都会的分，是则执行PlanA，否则执行PlanB搏命

【赛场小记】

Day0：平静的序幕

开幕式，还是那个熟悉的味道：气派的视频，领导的讲话

思绪不由飘忽到两年前

那时的我是那样的意气风发，为自己能参加这国内oi届的最高盛会而那样的兴奋着

那个少年又去哪儿了呢？

现在的我只能静静的坐着

等着命运最后的审判

一晃就到了下午，最后复习了一下便来到考场进行笔试

考场意外得冷，最令人害怕的是许多位置正上方有空调风直贯而下，在炎炎夏日带来寒风刺骨的VIP黄金体验

由于好奇手贱尝试了题库中提到的Ctrl+Alt+F2，结果进入了我不认识的界面

立刻冷静地找了另一台电脑，手速一波后成功在考前3秒进入了考试系统

虽然笔试一如既往的简单，我还是坚持检查了四遍，一直检查到了考试结束

看见笔试满分后长舒了一口气，告诉自己“已经先下一城”了，给自己壮了壮胆

在接下来的试机中先配置了机器，写了个快读拍cin，跟风写了FFT测速

还带上帽子提前适应了一下冷气轰顶的感觉，毕竟老倒霉蛋了

得知这次NOI中开了C++11后比较开心，感觉是时代的进步

晚上复习（抢背）了一下BM，看了一些常见算法

熄灯后忽然拉肚子了，但万幸在上了厕所后就没有持续下去

应该在11点半前成功睡着了，平安夜(雾

Day1：梦幻的开局

早上打开洛谷搜索“模板”，最后扫了一遍知识点

然后进入考场，其实这时心里感觉还是死水一潭，没有比赛的紧张感，也不知是不是好事

坐上座位，发现同校的选手有一半多都在以我为圆心10m为半径的圆内，顿时又安心了许多

比赛开始，按照原定计划开始看题

但是在T1读到数据时，瞬间察觉到了n<=50和w_i<=5这两个奇怪的地方，立即意识到了这题的算法是矩乘，于是稍加思索就得到了这题的标算

这时犹豫了一下，决定更改原有计划，立刻把这道题写出来

这是因为在判断出这是一道必须过的题后，立刻做出来可以避免思维干扰

由于对矩阵的知识稍有忘却，我花了1h20min完成了这道题的全部工作，包括写标算和暴力、对拍、手动出数据卡，把它塞进了文件夹中，这足以让我确信我已经获得了100分

这时我也逐渐进入了比赛的状态，于是按照原定计划思考了后两题

对于T2，我首先想出了容斥做法，然后对于链上情况想出了一个做法并成功拓展到了树上

但是我一开始对这个算法分析错了复杂度，以为这是O(n^3)的，并没有分，时间也到了，于是去想T3

对于T3，在观察到这道题的简化版是区间逆序对后，立刻识别出了这是不可做题，但是对于区间逆序对做法的忘却着实让我惊慌了好一会

我根据残存的记忆尝试了很久容斥，但做了无用功，在30min的时限才终于意识到了是有一个O(n^{1.5}logn)的简单莫队做法的

在快速确认了我对第二题没有新的想法后，我放弃了尝试通过其中一题的想法，立刻开始打T3的暴力和莫队

由于当时不会性质B，而且因为性质C太下了导致我默认了它不可做，于是我开始尝试对T2获得分数

在思考了好一会后依然没有更多的想法，觉得不能再无所作为了，于是打了dp和暴力，拍上了，这时才意识到这算法是O(n * dep)的，而且能过随机

能过随机这件事就让我开始兴奋起来，因为这么多个点，一般来说出题人总得卡各种暴力，而且可能还有一些点去卡正确性，是不可能一个点都不放我过的

所以我对代码进行了卡常、写了一个假的启发式、写了一些特判加速、又写了个优化(忘了是啥了)，满意的结束了对这道题的得分

这时里比赛结束还剩30min，我突然发现T3的C是很简单的，但这时再码KDT万一错了就没了(考试时傻了没想到扫描线)

我想起我之前在和网友讨论时听说的二维树状数组+哈希表写法，虽然我从来没有实现过，但这次开的C++11让我感觉这个算法在向我招手

还剩7min时写完了，但是没有过样例

我喝了口水，立刻给了自己一个底线：最后3分钟时无论如何停止调试，复原代码

非常幸运，我在倒数第4分钟找出了错，并且在倒数第二分钟完成了提交

底分：100+64+52

期望：100+80+52

一考完就碰到一个强大的srf，宣称人均过了T1和T2

听了他的讲述以后发现T2确实不难，但是不算太难受，因为我T2如果去写了标算就写不出T3的C了，这样一来大约也就亏了10多分，还能接受

查分前感受到了身体不适，感觉身体里有个东西在撞来撞去，但还能接受

屏住呼吸打开电脑，被分数吓到了：100+96+64=260

$T2$一开始是以为数据水被放过了一大堆分，后来跟西瓜交流后发现大约是出题人没有想到启发式合并的暴力，所以跑过了一些构造的数据 得知分数了以后心态发生了巨大的变化 因为说实话，在考前心里还是默认退役的，但现在金牌仿佛就只剩临门一脚了 心里反而紧张多了，因为希望后的绝望远比从没见过希望恐怖 下午跟jyg和队爷snz在操场上散步谈了谈人生，心情平复了一些，发现厉害的人厉害是有理由的 晚上确认了大约相对队线有$20$多分的优势，还是只能当没有优势来打 最后复习了网络流和字符串抱佛脚就熄灯了 ~~没想到的是今晚不是平安夜了~~ --- #### Day2：命运的抉择 $10:30$熄灯，一直辗转反侧到$11:45$，开始肚子疼 遂去上厕所，回来状态更差了，甚至开始干呕 拼命想让自己冷静下来，不断寻找着让自己睡着的办法，试过了背单词、数羊之类的，统统没用 很崩溃，躺在床上翻来覆去无能狂怒，万幸在这一系列过程中我终于累了，大约在1点半左右还是睡着了 早上起来，眼皮很沉，并且又拉肚子了，身体很难受，但精神状态还行 --- 考试开始，我先用1h执行了看题的预设，但是没有任何的想法，会的分数基本上看不见 似乎到了死局。慌张了一瞬，我立刻冷静下来，大胆做了两个猜测：今天是CTS难度，题目按照难度排序 于是我决定肝$T1

仔细地再次看了数据，发现m=n-2和m=n-1是关键性质，而给m=n-1的分必有高论

于是我写了暴力，跑了1k组随机数据，在m>=n-1时均跑出了解，但再m=n-2时就出现了一堆无解

我认为这个结论是对的，于是盲猜了一个贪心，通过了前者数据的对拍

但接下来我就走偏了，一直想着如何让m-=1,n-=2这样的事情，想了很久无果

但是T1拿35跑路是必死局，于是我决定写乱搞

观察到对于随机数据有解的状态方案很多，我决定卡时跑多次，每次对于序列random_shuffle，选择最前的点和它后面第一个能够一起填出一个K的位置来填

写完以后发现它能过随机，指拍了几十组都没WA，但把卡时改成1/{10}就危了

因为感觉多测checker太难写了，感觉写完没有时间写后面两题的暴力了，遂放弃

当我准备最后在肉眼观察一下大样例就弃疗时，突然发现大样例的方案其实是错的，但错得不明显导致我第一遍没看出来，吓出一身冷汗，差点爆零

调对，又按捺住焦躁的心情又肉眼差错了一会，终于结束T1，这时已经过去了3h10min

T2$题面非常长，虽然看起来可做，但当我假了两次以后立刻就失去了梦想，开始写暴力，写完立刻转$T3 回头看$T2$是否还有分拿，一想发现了性质4是好做的，懊悔了3秒立刻放弃了Rush这种不切实际的想法，转而尝试手动判了3层，希望可以水到分，然后开始等死 一考完，交流后发现我T3以为的搞分其实是能过边权一样的，感觉平白无辜赚了$15$分 底分：$45+16+20

期望：85+20+20

考完发现大家的分大多都是???，而且我的猜测都赌对了，心态稍安

临近查分，我身体开始逐渐出现明显的不适，我尽量尝试让自己全身心专注地投入游戏当中来逃避，但每当一局结束，恶心感就如飓风中大海的波涛一般，一浪接一浪地奔涌而来，将我淹没

来到赛场前，发现复测被咕了

过了十分钟后，我感觉到我已经恶心到快虚脱了，于是独自来到了操场，躺了下去

看着蓝天上白云悠悠，心里想着，如果第一天这样都进不了队，那就是我不配了呀，回去好好上学就是

这样心情慢慢平复了下来

终于出分了，我深吸了一口气，以尽可能平稳的心情打开了电脑

--- 接下来就是焦急地等待出线、被叫出去摸了一下T的保送协议，直到一块有着让我安心的重量的金牌挂在了胸前 还是进了啊 --- ## 【马后炮】 ##### 一、其他选手的实力是远高于我的预料的。 我预计的Au线是$420-430$，但是在很多实力强劲的选手已经在省选中被省队名额或者$1/3$限制卡掉了之后Au线依然达到了$447

我去之前以为我大约能有四成的把握Au，现在看来或许只有两成吧

依靠发挥击败了一些应该说实际上比我强的选手，感觉有点“胜之不武”

二、仔细一想，其实这次也不能全说是运气好了，主要是发挥比较完美

因为比队线高了19分，Day2T1的乱搞感觉是很难被卡到50分以下的，所以我出队要么挂了两个Subtask，要么Day1T2的乱搞被出题人精准识别到了并且卡掉了我六个点以上

虽然这题的数据大约已经不算是用脚造的了吧，因为这题本身就是难造数据的那种，并且已经卡掉了一些剪枝乱搞，但是还是感谢ytq哥哥的不杀之恩（

三、或许如果考试时能再冷静一些，Day2T1是可以做出来的

但是马后炮的说，在当时已知Day1拿到了分数优势的情况下，选择乱搞保命而不是冲刺或许还是正确选择吧

Link:退役杂谈-我与OI

另：欢迎查看去年就进队把我摁着打的江苏队长snz的游记

传 世 经 典

snz的NOI2020游记

snz的NOI2019游记