NOI 2022 After Story ~Silent Answer~

· · 个人记录

或许这是与比赛经历关系不大的一部分。

我先说说我的 D2T2 做法，因为实在是太乱炖了，不知道有没有大神可以来证明一下。

首先问题可以变成：每个位置要么确定了，要么有一个下界，求整个序列的逆序对最小值。

具体方法：首先因为给出的区间 [l_i,r_i] 里面全都不小于 v_i，可以先求出每个位置的一个下界。然后又要这里面最小值恰好是 v_i，那么我们从后往前确定。遇到一个区间左端点，如果这个区间里面还没有恰好为 v_i 的，就把这个区间里面第一个下界为 v_i 的认为是需要恰好为 v_i 的。如果不存在这样的位置就是无解。

可以证明一定存在一个最优解满足这个限制（这个不难证）。

然后对于性质 AB，所有下界都是 1。那么从前往后，直接对于每个位置，找到在仅考虑已确定的位置（包括一开始钦定的数和前面所有数）的前提下，贡献最小的数，若有多个取最大的。

容易发现这些数是递增的，所以内部没有贡献逆序对，所以这确实取到了最小值。

回到原问题。

这时因为有下界的限制，我取了不小于下界的贡献最小的数 x（有多个仍然取最大的），但是我随便画了几个图感觉这就不一定单调了。

（是这样吗？如果实际上是单调的那就和别人的做法没有区别了）

但是我发现，如果存在不单调，也即前面有一个比现在大的 y，而且 y 那个位置的下界比 x 小，可以交换这两个数，显然更优。

然后交换完了，可以证明考虑已确定位置的前提下，当前位置最优的数还是 y，因为我在多个时取了最大的。

同时，一个位置只会和前面交换一次，不然之前就交换完了。

问题就是这个后效性太迷惑了……真的不会使前面变一变更优吗？

哦另外，如果直接模拟这个交换，估计是会 TLE 的，但是我们发现前面交换对后面贡献没有影响，所以可以把交换全部放到最后再做。这也就相当于把所有下界位置上的数拿出来，贪心重排。贪心就是找到比下界大的最小的填。

所以这个做法太迷惑了……怎么证啊，等个大神教教 /kel。

说实在，我从来不觉得我有集训队水平，可能做题能做但是考场上总是会犯各种降智，这当然也是能力的一部分。

事实上我在大多数正式比赛都是超常发挥（？？？），从初三开始就是，同时也包括了去年省选，今年省选和 NOI 三场都是 day2 翻盘。

但实际上，总体看下来，今年 NOI 是我发挥的非常不出彩的一场。

这两次省选我虽然 day1 都确实打得稀烂，但是 day2 真的还是比较出彩的，这次 NOI 的 day2，我感觉我只是莫名其妙猜出了 T2，而且剩下两题都很不能看。

（事实上，要是运气没到，T2 没猜出来，确实进不了。）

我在两天只过了两道题，剩下全是靠暴力堆出来的（也并不是高分暴力），这能进集训队就有点搞笑了。

而且看到我游记里面也还犯了各种低级错误，比如在知道大样例放水的前提下还不测速不对拍，最乐的还是 D2T2 卡常前不存代码。

所以我究竟相对其他选手有什么优势呢？

没挂分。

（这也确实就是运气吧，毕竟大样例放水我都没管。）

事实上一直以来就是这样，一些 Ag 上位会的分比一些 Au 下位会的分多不少，但是一挂就寄了。

尤其在今年，本来整体分数就不高，D1T1 还有各种挂分（甚至爆零，幸好没卡 long long），D2T1 也有各种被卡哈希（事实上我用的质数哈希是错的，还得感谢放我一命），不挂分显得尤为重要。

综上所述其实我这场完全打的就是运气，正好运气也打在了不挂分上面。事实上我的整篇游记看下来也确实没啥出彩的地方是吧。

生日+出生地 buff 果然好用。

这里劝告一句后来人，稳中求稳，会的分不多不是重点，重点是尽量全部拿到。我在赛场上的若治行为一定不要再现了，鬼知道运气什么时候会到。

知道大样例放水了一定要测速对拍，不会造数据也要仔细检查。大幅改代码前一定要备份。

是这样的。

看过我博客园的都知道，我这一赛季就没写过正经游记，大多是走个流程。

上个赛季的省选和 NOI 可能用了一点心但还是很短。

但这次的游记估计差不多有我整个赛季其它加起来的两倍。

一个是因为这确实是我最后一场认真的正式比赛了，那肯定得认真写。

另一个是，比赛之外的活动也写了很多。

（此处赞美主办方，组织得太好了。）

顺带提一下去年 NOI，那年我完全是窝在自己宿舍里不出去，比今年还夸张，自然也就没啥好写的。

可能，要是没有教练给我多买的 100 个徽章，我就拿着 30 个和自己省内换完差不多了，我也还是不敢去找群友吧。

（此处感谢教练。）

或许在考场比赛之余，与其它选手互动，才是最享受的过程。所以我也会在游记里把这一部分也写得很长，即使是流水账也想写下来。

但是我也并没有抓住这个机会。

兔群/群友并里面整天在狼人杀啊，我因为不会也不敢去。

不会又怎样？

现在想来当然是后悔，即使是每一局都当敌人的队友，都还是很有乐趣的，就宁愿自己当个乐子吧，大家都开心，而不是让群友记住自己的机会都没有。

正式比赛之余留下那么多时间，哪是用来躺在宿舍里的？

很可惜我到 day1.5 晚上才明白这个道理，已经晚了，还碰上突发疫情，也就永远错失了这个机会。

感觉也和许多群友说的一样，不知道下次见到群友是什么时候。

没有见面的机会不是最痛苦的。

只有一次更痛苦。

只有一次还没把握住更痛苦。

CTT 估计还能和一部分群友再玩吧，只是剩下的，要成为永远的遗憾了。

或许在哪里见过类似的话，可能社恐就是这样。

回忆录或许早晚会写，但是估计真的就非常长了，无限期咕着吧。

不太敢摆一年，所以决定读预科了，明天就出发去 BJ。（有无面啊 /se）

接下来可以认为是和 OI 说再见了。

感谢父母和所有提供帮助的亲人。

感谢各科老师，包括教练和文化课科任老师。

感谢同学，学长和学弟。

感谢所有给予过帮助和/或快乐的群友。

感谢自己。

……

感谢 OI 之旅和旅途上的一切。

总觉得写得还不够满意，可能会再来补一补吧。