NOIP 2025 游记
qifan_maker
·
·
生活·游记
// The Moon Lights, Thanks The Moon.
～11.16
前情提要：CSP-S 2025 挂大分仅获得了初中生 \text{rk26}，详见 CSP-S 2025 游记。
从 CSP 打完到正式确定 NOIP 参赛资格之间经历了很多希望与希望破灭。下定了决心如果能参赛就停课训练。
由于还未通过 CCF 的正式审核，$\text{11.16}$ 还是去了学校。在学校想了想发现时间非常紧张，果断决定 $\text{11.17}$ 开始停课，如果打不了就在家自己 vp。
### 11.17～11.27
第一次停课，调整了一下作息。加训了组合数学，计数，DP。得到了 LHQing 的技术支持。月亮好闪, 拜谢月亮.
### 11.28
前一晚在外面随机游走到了凌晨一点，紧张的情绪得到了一些缓解，早上睡了个懒觉。下午前往南昌，住在了 gb_lw 家里。晚上和 gb_lw 复习了一些板子，$\text{10:50}$ 睡觉，轻微失眠。
### 11.29
比赛日！
早上 $\text{7:15}$ 起床。$\text{8:00}$ 吃完早饭前往南昌二中，路上意识到忘了 tarjan 怎么写了，紧急复习了一下。$\text{8:10}$ 进考场，调了一下配置，发现无法使用 fsanitize，尝试了十分钟无果后选择在命令行编译测试 re/ub。有点担心被卡 T1。
$\text{8:30}$ 开考。读完 T1 发现是个背包 dp 状物，此时肚子爆了，去了趟厕所，蹲着突然意识到每颗糖的权值都是 $1$，显然是贪心，然后一拍大腿发现没带纸。想了两个假做法，写了一个按题意模拟的优先队列贪心，但是无法处理连续选择同一种糖果的情况，$\text{9:10}$ 发现假了后用了 $\text{10min}$ 想到了正解，只要某种糖果可以连续选择，那么选择它直到无法选一定是最优的，发现在原来代码上改改就能过（缺点是写成了一坨，赛后发现只需要一个排序一个循环即可），$\text{9:37}$ 过了 T1 大样例。
此时比赛还剩 $\text{3.5h}$，虽然花了一年才过 T1 但是反正是过了优势在我！冲一冲 $\text{200pts}$ 应该有了吧！（嗯。）吃了根士力架，把后面三题过了一遍，期间不放心 T1，造了一些 corner case check 了一下。
$\text{10:00}$ 左右开始进军 T2，读完题发现这他妈是啥，我怎么只会 $\mathcal O(2^{n+1})$ 的 $\text{20pts}$。此时还没有意识到这题的危险性，尝试从特殊性质入手，试图想出正解。$\text{30min}$ 后发现一无所获。把特殊性质 A 的 $\text{4pts}$ 写了，然后想了想 $m=2n-1$ 的情况，发现无论如何都能取到最大，答案也是 $2^n$，再看 $m=2n-2$，发现只有最小值$\times 2$ 大于次小值的情况不合法，用 $2^n$ 减去即可，写完测了样例发现不对，还需要判断最小值不等于次小值。此时又过去了 $\text{30min}$ 获得了 $\text{12pts}$ 以及还没写的 $\text{20pts}$ bf。上了个厕所洗了把脸决定把 bf 写了，写了一半意识到不对劲，怎么犯唐把 $2^n\times 2^n$ 算成了 $2^{n+1}$，$\mathcal O(2^{2n})$ 的复杂度只有 $\text{12pts}$，思考了一下把 check 的 $2^n$ 复杂度优化到了 $n$，总复杂度 $\mathcal O(n2^n)$ 就对了。写完调了很久，$\text{12:28}$ 过了样例。
此时还剩 $\text{30min}$，读完 T3 发现题意比较清新，长得非常可做，想了个贪心发现假完了，想到对于一颗子树只有两种状态，一是自己作贡献，二是为其父节点作贡献，感觉比较对，但是剩余的时间已经不足以继续思考它了，决定求稳先把 T4 暴力打了再回来写 T3。
T4 读完题直接按照题意模拟写了个巨大 $\mathcal O(qn^4)$ 的暴力，发现怎么一个点都过不了，套了个前缀和优化了一个 $n$，发现输出要 $\bmod ~2^{64}$，用 ull 自然溢出即可，但是处理了半天怎么输出还是负数？？发现用 `printf("%lld")` 输出 ull 爆了，但是发现不知道 ull 如何用 `printf` 输出，于是改成了 `cout` 便对了。
最后 $\text{10min}$ 写了个 T3 的很没道理的骗分，检查了一下各道题目的 `freopen` 就交了。把草稿纸顺出来了。
出来之后算了下发现只有 $100+32+0+5=137$ 分，感觉倒闭了，问了一圈发现大众分疑似是 $100+20+8+15=143$ 分，好像没太爆？出来后合了若干张影，等了会 gb_lw，得知他和我同分，回去的时候发现洛谷难度评了黄紫黑黑？？？？？？？？？？？这下 NOI Practice 了。组题人的【数据删除】飞上天了。
晚上得知很多选手因为这场比赛而退役了，心情有些低落。回到家感觉很累，和群友联机了会 mc，大家似乎都没什么兴致了。
### 12.1
担心 T4 的 $\mathcal O(qn^3)$ 过不了 task 1，晚上回家复现了一下发现跑得飞快，算了一下发现带了大概 $\frac 1 6$ 的常数，这是好的。
### 12.3
$100+32+0+5=\boxed{137}$，一分没挂，江西 $\text{rk25}$，初中生 $\text{rk4}$。