NOIP 2024 游记

· · 生活·游记

时间：2024.11.30

坐标：上海市曹杨二中

607机房

Day -\infty

csp-s 喜提 200 分，未达标 7 级。

C 写了两个小时dp最后暴力都挂完了。

Day -1 & Day 0

脱产两天半训练。

考前连下三盘面棋，三连败，可能加起来输了快两百目。

把4条装的健达换成10条了，主要是不够吃。

Day 1

7.15 起床。好像不是很冷。

7.30 吃早饭。菜谱：半杯牛奶，包子，烧麦，鸡蛋。吃完饭出发前往曹二。

yjh为什么还没起啊，怎么去华二了。

8.17 到达考场。人貌似不是很多，门口简单逛了几圈就进去了。

横幅设计的还挺有科技感的，比华二的花草自然风好看一点。

8.25 进机房。一个正常的机房。

csp-s在隔壁606机房考的，六个人一张桌子，围着坐，右边小孩写了一个小时开始玩火狐和surf。很挤，出去还要跨椅子腿。

8.30 开始考试。每个题简单瞄了一眼，感觉 A 又是签到。

8.40 想 A，没过几分钟想到貌似可以在每个字符串隔断点往前把统计做完，开始写。

8.55 写完了。把样例扔进去，不对。想了一下，发现贪心明显错的，显然每个隔断点后另一个字符串的部分也会对答案产生贡献。心态小崩。

9.05 发现可以在遇到第三个不同字符串隔断点时统计前两个相邻隔断点之间的贡献。感觉上应该是对的，开始写。

9.25 比较恶心，写完了。样例放进去又调了二十分钟，过了小样例。大数据扔进去，前八个是对的，第九个点答案八百多，代码跑六百多；第十个点答案忘了，跑出来负三千多万。不想调了，跳掉。

9.55 开始看 B，第一眼就看到貌似每个确定数之间的一部分各自是独立的。

10.00 估计推该公式难度不超过高联一试压轴，开始推递推。先手算了相邻两个数都确定时（即间隔为 1）公式 v^2-v+1，间隔一个非确定数时公式 v^4-v^2+v，感觉推完递推之后可能是倍增。推了两分钟倍增发现有点恶心，决定先推递推。

10.10 轻松找到递推公式，显然是一维且只依赖前一位的，讨论首位是否起到限制即可。公式 f_n=(v-1)v^{2n-1}+vf_{n-1} 。先把前后的公式 g_n=v^{2n} 算出来，然后要了张新草稿纸，先把 1e6 内的点写完。最后带间隔为 3, 4 进 f 找规律，发现每个递推都是三项式，貌似次数很有规律，代数方法算一下就把公式 f_n=v^{2n}-v^n+v^{n-1} 推出来了，快速幂简单实现。

10.40 B 调完了。又回头看了眼 A，还是找不到问题，遂放弃，开始看 C 和 D。

11.00 去上个厕所，上完了先看 C。看完发现没想法，决定先看部分分。 c=18 的链显然答案均为 1，c\in[19,21] 的菊花图误认为是 \frac{1}{2}(n-1)!，先把这四个点写完了。

11.30 简单有一点思路，可以先以边为根本建图，然后扔进去跑 k=1 的暴力，这样能过 c\in[1,3] 三个点。把这三个点写了，并试图获得一些提示。

11.50 好吧，没有获得任何其他的分，看出来一些类似于强联通分量的东西，但没有进一步的想法。感觉上应该想不出来正解了。剩下的部分分都看过了，无一例外不会。

12.00 开 D，一眼看上去像是线段树维护 lca。仔细读了一遍题，以为朴素线段树就能过掉 [6,13] 的点，写了遍线段树。写完发现貌似全过不掉，O(qnlogn) 好像过不掉 n,q \leq 10^5。

12.20 挣扎一下，发现大样例跑的还挺快，0.2s 左右跑完。因为 A 还没过，打算 12.30 回头看 A。想用st表优化常数，5分钟没调出来，不敢写了。

12.30 回头看 A。又手算了一遍模拟过程，很快找到了问题所在，两个地方忘清零了。

12.36 A 大样例过了，大喜过望。遂试图搞出 C 的 [4,10] 七个点中的任何一部分，失败。

12.48 实在想不出来 C ，开始全面检查。

12.52 检查完毕，A B D 都一切正常，唯独 C 的 [19,21] 出了问题，完全不对。一下子慌了，赶紧手算。

12.55 一边想 C，一边检查文件夹。

12.59 实在查不出来了，最后还是没发现公式问题。赶紧把 C 的代码恢复。

13.00 检查大文件夹的准考证号和命名。极域好像出了点问题。

13.02 极域恢复，提交代码。

13.07 签字出了考场。貌似曹二都是 csp-s 没考好的，出来听到很多 A B 写炸的，当然也有ak佬。

13.15 上车回家。披萨好吃。

估分：100+100+16+[0,32]=[216,248]。

总结：发挥总体上还可以。前一个小时心态太炸，满脑子想 xxx 能不能做出来这个题，A 做不出来就废了。A 时间省出来有机会 D 多写一点。最后半个小时策略有误，C 的 [19,21] 部分应该是能提早检查发现错误的。