2025 NOIp 游记

· · 生活·游记

day -1

### day 0 **6: 05** — 起床，吃早饭 **6: 30** — 出发 **7: 15** — 到达南京航空航天大学将军路校区，与同学合照。碰到了 chennie，pmd，cmh。 **7: 35** — 进考场，关手机 **7: 40 ~ 8: 30** — 试机。今年南航的键盘鼠标换新了，比前年好用，而且比南外宽敞。这下南航 >> 南外了。 敲了总板子、拜谢 chennie 板子、modint 板子。然后去了两趟厕所。 **270** — 开 T1，然后显然是两两分组，选最小的 $x_i + y_i$，剩下的一堆 $x_i$ 从大到小选。枚举选几个就作完了。10 min 过了大样例。 **260** — 开 T2。最开始题读假了，以为是先求总的最大值，再求有几种方案能达到这种最大值。想了半天怎么求最大值。后来发现是求有几种方案贪心贪的是该方案的最优解。然后还是不会。去看了一眼 T3。 **250** — 思考了很久有哪些情况取不到最优解，发现是如果有两个物品 $(a, 1)$ 和 $(b, 1)$ 被选了，有一个物品 $(c, 2)$ 没被选，且 $c > a + b$ 的话，那就会被卡。现场没证明充分性，但是感觉已经充分了。 我决定小容斥，用 $2^n$ 减去不合法的。想到要卡到两个选了一个没选，画了半天图，然后发现最大化 $c$ 很不错，因此枚举这个 $c$。 然后同时考虑到这个方案要能选得出来，还要存在 $a + b < c$，如果钦定 $a < b$ 的话，发现枚举 $b$ 很不错。然后剩下的一个组合数就完事了。到这里我还不是很自信。 **240** — 刚写的 modint 板子派上用场了，快速地写了一下，一边写一边调整了一下思路。然后测小样例。发现挂了。 **230** — 注意到，我的输出跟答案只差了 $1$。仔细一看才发现是没考虑多种物品价值相等。改完就过小样例了。然后大样例也过了。 **220** — 感觉非常顺利，说不定能阿克呢。但是仔细地想了一会儿 T3 发现并不会。然后又去开 T4。 我一拍脑袋发现如果 $R <= 2L$ 的话，就能左查一遍右查一遍直接得到答案。这样每个询问就能拆成 $\log n$ 个。总共只有 $O(q\log n)$ 个，但每次询问都是 $O(n\log n)$。过不了。因此我发现我如果把所有询问统一考虑，是不是就只有 $q + \log n$ 地询问了。那我把所有询问，总共 $1000 * 50000$ 个 `long long` 存下来，三百多个 MB，正好。我出 T4 正解了！！！ **180** — 我激动地去上了个厕所。然后回来写代码。先敲了个不带修改的线段树，然后开干。花了半小时才写完。 **150** — 悲报：挂大样例了。还把我电脑卡关机了，吓得我叫了监考，监考说直接开机就行了。然后就好了。 我花了好久调试了一下才发现，其实不是 $q + \log n$，是 $2q + \log n$，然后空间翻倍，那我假了。 **120** — 于是回到 T3。根据模拟赛经验，只写两题不太行，我得再出一道题。但是我显然还不会 T3。但我 T4 假了，只能干 T3 了。我觉得要用 $dp_{i, j, k}$ 表示结点 $i$ 的子树 $\text{mex} = j$，有 $k$ 个自由点，的最大得分，然后稍微写好一点就是均摊 $O(n^3)$ 的，能骗 48 分。 有点难写，花了一个小时。 **60** — 突然感觉 T4 空间这么紧，感觉我的方法不像正解。于是决定开始骗分。先把刚才的方法丢到 `namespace` 里，用来过 $q$ 或者 $n$ 比较小的。然后 A, D, E 用上面的方法每个询问最多拆两下，因此暴力拆。又发现 A 直接这么搞有点慢不知道为啥，然后就特判了一下。然后用三个 namespace 实现了最多 72 分。 **30** — 最后把所有代码全测一遍，有两题关了同步流，期望多草过一些点。 **10** — 记录文件大小。才发现 T4 写了 7000 字节。 然后我就发现了： ``` // assert(freopen("tree.in", "r", stdin)); assert(freopen("tree.out", "w", stdout)); ``` 幸好发现了。 **13: 10** — 听大家说这次比赛很难，所以稍微放心一点了。希望能骗到 300 分 **20: 00 ~ 21: 40** — 打 abc，没能 2400 上黄，但至少涨分了。 **22: 00** — 太困了，没打 div. 2。睡觉。 ### day 2 摆了一天，晚上没打 arc，因为要回 whk。 ### day 3 ~ 5 whk ### day 5 放学才知道，283 分。T4 略低于预期，但问题不大。 省选启动！