游记 - NOI Online 2022

# NOI Online 2022 游记 *Date: 2022-3-26* ## Morning: Senior 上午在七楼机房。 老师给我们的寄语是：权当增加比赛经验，练手。 ### T1 读题的时候推了一下，发现只需要记录每个点在栈中的前驱在不在当前区间内，然后就变成是主席树水题了。复习数据结构。 ### T2 不会，打了个暴力。就是，按集合从大到小排序，每遇到一个集合就分两种情况：是“开创者”还是“依附者”。弄个 map，每次存最后一个包含该数的集合编号，然后用常识判一下就完了。依据是必然有大的集合包含小的集合。 ### T3 不会，拿了前 20 pts 部分分。10 pts 是暴力，10 pts 是 $m=2$ 时的 $2n\sum a$。 ### 赛后 洛谷给我估了个 $100+100+20=220$。 交流的时候，了解到学长 T1 用了离线树状数组的做法，又意识到 T2 本来用数组的地方用了 `std::map`。你好。 最终拿了 $100+50+20=170$。 突然发现，T2 有一个致命的问题：一旦出现两个完全相同的集合，它就无了。 打完之后，切身感觉到自己目前的一个奇怪的处境：对于熟练的东西很轻松，对于不会的东西根本不会，拿到的分微乎其微。 T3 后来了解到是很有趣的偏序。但在赛时，我根本不知道如何想。事实上，我知道二维数点，也知道 Min-Max 容斥，但就是想不到。 ## Afternoon: Junior 下午回到六楼。 没有七楼爽。 ### T2 推了一个多小时的式子，最后大道至简地用图示确认了结论是 $\frac{z}{x\sqrt{gcd(\frac{z}{x}, x^2)}}$。 ### T3 不会，直接打了个逆推的 dfs。就是说，从目标往前推，如果遇到 `-`，就尝试在前或后加一个 `X`；否则，判断当前可不可能然后往下搜索即可。加了一个小的剪枝，当当前字符串已空时，答案就是 $2$ 的 还需要走多少个 `-` 次方：这个你就想，无论如何总是要删空的，每一个 `-` 只有 $2$ 种走法，就完了。 当时急了，不想做了，离交卷还有 1h 就溜了。 ### 赛后 我居然没有判不合法！！！ 我太危了。 更离谱的是，赛时我都没发现检测 T2 是否合法的一个关键：是不是完全平方数。实验证明，`pow(sqrt(n))==n` 这样的做法在一个极小的数据集里可行，但也只是极小，大样例没有一个 `-1`。 洛谷估分 $100+20+30=150$。 结束了！！！ 我想过 T3 会挂，因为我当时真的没静下心；但是我没想到 T2 能成这样。 实际分数 $100+100+80=280$。 这是否…… ## Result 学到了： 1. 了解了离线树状数组的技巧，可以避免书写高级数据结构； 2. 练习了有难度的数学题，巩固了数学； 3. 练习了骗分。 不好的现状： 1. 赛时静不下心，全忘了判合不合法，把数组用成 map，把就差一步的 DP 只留下 dfs，判完全平方数也写错； 2. 对于基础知识的高级运用还是想不到； 3. 对于复杂的 DP 模型还是建不起来。 我觉得，这些东西还是应该在平时的练习里面多加感受与总结。另一方面，我近期的个人状态也不太好，希望能调整过来。