SGNOI 2025 Finals 游记

lumid · 2025-03-24 20:20:18 · 生活·游记

新加坡 NOI

Mar 15 收到的 email，今年可以参加新加坡 NOI 蛮开心的（虽然成绩是非官方）

Day 0

坐火车回KL zzzzz

盲猜：

1. 排序
2. 图论
3. DP（线段树）
4. 交互题
5. ？？（很多 Subtask）

Day 1

紧张

09:30:\ 睡醒收到 email 说邀请函里的报到时间 "12:30-13:00" 是错的，改成 "11:30-12:00"...

10:00:\ 尽快打印准备的模板，但是有问题所以只打印了几页

11:40:\ 到 Monash 大学门口，很贴心还有人带进去比赛地点\ 尽快写了写 Practice Contest 的一题，发现我 VS Code 还没调平时用的设置 lol\ 交了一发但是评测很慢，有点担心比赛会出现类似状况\ 然后是 Monash 广告时间，顺便去 IOI 2022 网站下载 ffmpeg\ 比赛快开始前有点头痛 qwq 吃了药好一点\ 目标：250 / 500

13:00:00:\ 比赛开始\ 虽然本来计划好先读完题再做，但是读完 P1 以为想到了所以就开始写，结果写完样例不过才发现引爆地雷也花钱（每次都急性子！！！）\ 这时候正确的做法应该是先读其他题再继续想，但是... 😓\ 然后实在是太冲动了，没想好好就一边猜结论一边写。交了好像两发 WA 后才冷静下来想\ 又 WA，发现忘了排序

13:35:45:\ AC P1\ 现在才读其他题\ 五题里有三题 grid lol，NOI stands for NxMgrid OI\ P2 一开始没有什么头绪\ 观察到任何 t[i] 对兔子的相对位置不影响，用 Subtask 证明这个猜测是对的\ 想了好久，感觉需要区间更新，但是区间形状很奇怪\ 发现可以 "旋转 45 度"：每个兔子的移动方向都能被分成一个或两个 (\pm 1, \pm 1)\ 可以对每个 t[i] 区间更新，但是觉得应该不会 P2 就有线段树了吧 qwq\ 然后发现按 r[i] + c[i] 排序后用栈就可以算，然后对称地按 r[i] - c[i] 排序算多一次\ 评测只有最后一个 Subtask TLE，这题竟然卡常 😭😭😭😭

15:26:10:\ P2 把 map 换成 unordered_map AC 了？？\ 怕赛后会用卡 unordered_map 的数据重测，试着想了想 O(n \log m) \rightarrow O(n) 的优化

15:39:37:\ P5 Subtask 1 写写过了

15:42:51:\ 感觉不踏实，最后 P2 用 map 和快读 AC 多一次\ 从这里开始就只是做 Subtask\ P3 想到 Subtask 3 的 sol 但是 WA（赛后跟朋友讨论发现想法是对的，可能是代码实现问题）\ 发现 Subtask 4 （没有双向边）可以转化为对每个点 u，存在一个集合 S_u 使 l[u] = 1 + \sum_{v \in S_u} l[v] 且 (u, v) \in E, \forall v \in S_u。遍历 u 然后用 0/1 背包判断即可

16:00:17:\ 写写写，WA？？（见下文）\ 尽力想了 P3，没头绪。接下来交了几发也 WA\ 算了，做 P4。

16:59:08:\ P4 Subtask 1 Bitmask + DFS 过了

17:06:49:\ P4 Subtask 2 过了：如果 a[i] 和 b[i] 行都没有特别方块则答案为 2，不然为 1。

17:27:46:\ 比赛最后一小时才发现 P3 Subtask 4 代码里写 memset(dp, 0, sizeof(0) 😭 改了才过\ 有点可惜，因为 WA 让我以为结论是错的。如果早发现可能可以想更多 P3 的解

18:00:00:\ 比赛结束\ 虽然分数没达到目标，但还是满意自己的表现，能做的 subtask 大多数都有做到\