NOI2022 游记

· · 个人记录

有去年集训队打银了，我不说是谁。

不过现在感觉根本不能算是集训队啊，只会做无脑题的人也配这个称呼吗？

比赛

笔试

今年笔试不是现场出分，我不是很懂。不过我感觉自己是满分了，好感动啊，终于有一次正式赛满分了。

记两个难题：

  1. 复评阶段忘记了自己机位的密码，怎么办？

A. 自己解决

B. 请求工作人员帮助并承担总成绩扣分的处罚

答案：B。分析：pdf 文件中明确写出丢失密码条扣 5 分。即使你选择的结果看起来多么魔幻，也要相信这一点。《如果不能保证分差>=5，就不能进行复测，这其实是一个赌局》

  1. [多选题] 你

A. 考试前不能翻试卷

B. 考试前不能碰键盘、鼠标等外设

C. 考试前不能登录系统

D. 在考试中使用网络。

答案：ABCD。分析：我的一个同学选了 ABD，理由是这三点 pdf 里都写了，但 C 没写。我问他不碰键盘怎么登录系统，他说他也不知道，但他感觉就这么写。所以请你注意做笔试题时还是要做一点正常的分析的。还有一点是这四点其实在考场外的须知上有，那些须知被书写在了考场外的一个大牌子上，你如果以后打 NOI 考笔试前可以先去看一下。

Day 1

一开始看 T1 感觉只能 2log，想了半小时后突然发现更改线段树存储的信息后可以多树同时二分，在 9:00 的时候写完通过了所有大样例。

来看 T2，但一开始把题读错了，以为第一个操作是每次把一个数减 2。经过一些尝试没发现什么性质，决定先解决 k=0。我将序列差分，然后写出了一个 DP，但无法通过样例。调到 10:00 时，一些小数据已经通过了，而有一个大数据我发现手摸和程序的结果是一样的，但就是和样例不符。于是我重新看题，发现题读错了 …

于是我去看 T3，看了好久终于看完，但还是看错题了，以为边集是可重的。思考一会就得到了一个基于 BFS 的预处理 O(n^2) 单次询问 O(1) 的算法，写了好久调了好久，因为交互库实现太诡异调的很费劲… 结果到 10:30 时发现又把题看错了！！！

感觉要寄了，不知道说什么好。先回去看 T2，再推推性质发现什么 0 把序列分开，1,2 都比较特殊。然后我就认为其它数是几乎等价的，在尝试了若干例子后决定编写一个与 AGC022E 比较像的把栈压入状态的算法，我的栈中存储 a 个 1 后面跟着 b 个 2，根据新加的数来改变 (a,b)。写完后跑了一下通过了样例。本来有 65536 个状态，但实际跑了一下发现有用的只有 129 种，顿时以为自己稳了。但细想发现不能通过题目，因为小数据表明 k 并不是越多越好，所以我认为需要 129^k 的复杂度才能解决原问题。于是我只写了 k=0 或 l_i=r_i 的数据，它们的样例我都通过了。我还进行了对拍，但由于命运的安排，我的暴力其实就是这个自动机的最暴力的写法，于是它们拍上了。

感觉这个分也不算太差，于是就去看 T3。想到了一个预处理 O(n^2) 单次询问 O(1) 的长链剖分算法，需要打标记。感觉能拿 30 多分还是不错的。于是就开始写，到最后也没写完。这题直接爆零了。

最后 10min 突然发现 T1 的大样例没有删除操作，再回头一看发现自己的链表完全写错了，于是以极快的速度更改了程序。

出考场以为自己是 100+55+0。

一堆人说 T1 要开 long long，什么意思？原来是因为询问的集合可重啊，哈哈！我也寄了。

但是下午看成绩发现是 95+20+0，这是怎么回事呢？？我开始调试 T2，发现了一个把我卡掉的数据。我以为是细节问题，于是补了一些细节，结果还是有把我卡掉的数据。我再一看，顿时明白我的做法完全假了。那它是怎么获得 20 分的呢？其实是获得了 n\le 5 的三个点中的一个，以及 l_i=r_i,k\le 100 的点，但 l_i=r_i,k=0 的点没过，神奇吧。

Day 2

今天 T1 的思考时间也就 10min，比 Day 1 的要短，因为我很快发现对于根的子树，若能直接匹配就可以优先删除（否则可进行调整），所以剩下的子树个数也就最多 k 个。进一步思考发现设计函数 f(u_1,u_2) 表示第一棵树 u_1 的子树，第二棵树 u_2 的子树是否能匹配。直接暴力加剪枝似乎很对，至少对于结果是 Yes 的树是对的，结果是 No 的树不太清楚，但试了一些例子没卡掉，于是就开始写了。9:00 的时候写完，吸取昨天的教训我写了对拍，但好像没有拍出错。为了求稳加了双模哈希。

T2, T3 都是奇怪的最优化题，其实这时就感觉自己要凉了。我先去看 T3，发现暴力似乎只能拿 8 分，但还是先写一个暴力后再思考题目。感觉能建最小割模型，就是构造 \sum w_{i,j}a_i\overline{b_j} 的式子，试了一下发现构造变量 [x_i\ge t] 似乎就可以做，至少能拿两位数的分。最大流板子都写好了，然后建模时发现不太对劲，再仔细思考一下发现这个式子似乎要求 w 是全非负的，而我并不能做到这一点，就寄啦。此时大概是 10:00。

T2 感觉按最小值分治然后区间 DP 能做 O(n^4)，但似乎无法优化。于是去想特殊性质，推特殊性质 A 时看错了一点，以为每个限制是区间覆盖 0 和区间必须有 1，如果按左端点排序则为了让区间们尽量满足 1 应该尽量靠右放，而逆序对也需要 1 尽量靠右放，因此贪心似乎是对的。写程序的中途发现我的观察出错了，是区间覆盖 1 和区间必须有 0，我以为贪心假了没有继续思考，完全没意识到我的观察只不多是与正确的题意反了过来，所以把解法反过来就可以。再看特殊性质 B 和 C，推出了特殊性质 B 中未被钦定数不降的性质，但仍然做不出来。

这个时候已经 11:00 了，权衡利弊后我决定变身暴力人，将特殊性质 A,B 的 O(n^2) 做法都给写了。其实本来以为特殊性质 B 的 O(n^2) 可以解决特殊性质 C，但结果发现不行。

最后的时间没有任何进展，因为每道题的分数都已经到达极限。

估分 100+56+8，但实际是 100+56+17，神奇吧。

忠告

聪明的选手即使 Day 1 挂了，也能靠 D2T2 翻盘。所以我没啥要说的。

但如果你的实力还不是很强（其实如果你水平很强建议你也这么做），我有两个忠告送给你：

  1. 这其实是我教练说过很多次的事情了，我以前都不当回事，但现在觉得还挺对的。请在追求高分前确保你拿的分比大家都会的分要高。具体来说就是你先把暴力给写了，特殊性质可以先不写，但最后如果这题不会是一定要去写的。
  2. 即使给了好几个大样例，且大样例看起来很强，还是要进行对拍。对拍其实并不简单，你需要思考怎样的数据生成器能更好地把错误抓出来，并且一定要在保证正确性的情况下编写暴力程序。

空洞骑士

来昆山前我完成度刚 80%，现在已经 92% 了。来给各位讲讲我都干了什么吧！

格林剧团

你可能需要上网搜一下攻略查询如何开启这个剧情，反正你让我找我是找不出来的。它其实在鹿角虫巢穴的一个隐藏空间中，我在那里自己探索时打破了第一个墙，但谁能想到还要再打一面墙呢。

收集火焰没啥好说的。第一次挑战格林大概用了 5,6 次，感觉最难的其实是躲地刺。建议你携带快速凝聚，如果没有它感觉就无法在格林的两次攻击间回血。其实也可以在地刺从地底冲出到收回去这一段时间内回血。他的血量好像不太厚，虽然我很难近身大概他三招才能砍一下，但好像 5min 就能结束战斗的样子。

不要放逐格林剧团，这样这个剧情就会直接结束。你可以不听布鲁姆说的话。

迪万可以把易碎护符转化为坚硬护符。 不过如果是自己玩怎么能想到啊啊啊。

辐光

辐光水平很高，你需要认真战斗！

建议携带各种防御、回血的护符。。不过感觉很多 boss 我都是这么干的

一阶段其实多试几次就没问题了，注意横屏的尖刺可以直接黑冲躲过去，火球也可以黑冲过去（好像可以直接把火球灭掉？？）

二阶段其实好像在平台上躲攻击比一阶段简单一些，因为场地更大自由性更高，但不好的点是你被攻击一下就会失去平衡，然后可能就会受到多次攻击，再掉出屏幕直接就寄了。所以其实是精确度的要求更高了。

最后向上走时注意别被光束干掉了，遇到辐光后直接快速砍它，我最后一局差点就死在这了。。

愚人斗兽场 2

影响比较深的有这些：

皇家水道新空间

看看攻略就得了。这种隐藏墙谁想的到啊！！！！！！！！！！！！！！！！！！

里面有寻神者的茧，需要简单钥匙。

哦对了还有个吸虫之母，不过它太拉了没啥好说的。

诺斯克

其实还没打过。。

upd：已过。考虑携带蜂蜜块和锋利之影，根本不用骨钉，掌握规律后当个 bot 就能打过了。

通道是被愚人斗兽场 3 整自闭后去深渊瞎走找出来的。

skicean

（我现在已经不知道他的 luogu id 是啥了）

热烈庆祝 skicean 入坑空洞骑士！！！！！！！！

别的什么东西

想到了再补。