NOIP 2024 游记

· · 生活·游记

初三，坐标 GD，估分 304.

Day -？

教练向学校申请停课训练，驳回，理由是我们 whk 太水了。

然而 rlc 和 bamboo 都外培去了

Day -17

期中考，一如既往的 A。

Day -14 ~ -1

考完期中就停课！停两个星期，一天一场模拟赛。

看似模拟赛，实则 DP 专训（

Day 0

考前不打模拟赛了，留给我们复习。把以前写的博客看了一遍，模拟赛看了一遍，然后打了 Ynoi、点分树、斜率优化、左偏树、Kruskal 重构树、整体二分（伏笔），以及 Dijkstra 和 欧拉序 LCA（伏笔）。

教练找每个人聊了一下考试策略：你去年 271 了，今年怎么说也要 300 吧。（伏笔）

os：去年是什么难度啊？今年我能保持 271 都不错了。

晚上十点半就睡觉了，健康身体。

Day 1

昨晚忘记关闹钟了，导致 6:10 的时候被吵醒了。

下楼吃早餐，本来想吃肠粉的，但是肠粉要等 10min，于是改吃小笼包，吃了六个。

然后我爸叫了个车，因为没赶上过这个红绿灯而就近拦了一辆出租。

居然 25min 到了，S 组要 45min。

在考场之前下车了，叫我爸用手机登谷给我看模拟赛打过的题目，图个心理安慰。事实证明没啥用。在路边看题的时候看到 bsdsdb 坐着车呼啸而过。

到学校门口，bamboo, Ethan 和 bsdsdb 已经到了。bamboo 展示了奶龙玩偶（

等了一会，rlc 也到了，于是一起进考场。

怎么全在一个考场？怎么考场里隔一个就有一个 SMS 的？

进考场了。监考老师叫我把脉动的包装纸拆了，给了我一把剪刀。遂拆了 10min。

并一不小心把无名指最上面的关节处划破了一个小口子，流了点血，但是问题不大。

发解压密码了，Forget 和 memory，有点忧郁系的感觉了。

解压，看题。昨天谷里还有说有叫 vote, string 啥的，骗人。

比赛

首先开题，四个题看一遍。T1 鉴定为分讨/贪心，T2 鉴定为 图论，T3 鉴定为 DP，T4 鉴定为 DS。看到 T2 感觉不太妙，有点像 2-sat 计数之类的，很迷惑。但不管了。

先开 T1。
想了个贪心，00 的没用，01 的优先满足，11 的尽量满足。感觉很对，因为 01 的自由度比 11 小，所以尽量满足01.
写写写 …… 然后过去 10min，测样例，怎么不对？
哦，读错题了，原来只能交换相邻的。

但是思路还是一样的。感觉代码有点难写啊，又要讨论各种端点的位置关系吗。

根据我对自己的了解，真写成分讨就 GG 了。所以想了一下怎么写。想了一下扫三遍就可以了：第一次把 00 的贡献算了，第二次求 a,b 的自由段，求每个自由段的字符个数，顺便把 01 的满足了。第三次用剩下的自由字符尽可能满足 11 就行了。
开写，9:00 完工并测完两个大样例。造了组极限数据只跑了 0.7s，感觉很稳，丢了。

看 T2。什么单向 2-sat 计数？？？我意识到真这么想包写不出来的，所以上了个厕所。回来意识到自己神经了，两个固定变量之间的 (a,b) 是完全独立的。而这两段之间就是一个 v 的次方。排个序上个快速幂就行了。

10min 写完，怎么样例 RE 了？？？哦，原来是会出现 a 相等的情况，模 0 出 bug 了。特判 + 去重之后过大样例了。极限数据跑 1.1s，有点慌，但是不会优化了，不相信有纯线性的做法，肯定是本地跑的慢，丢了。此时 9:30。

1h 弄完前两题，有大把时间弄 T3T4。先上个厕所。

回来看 T3T4。T4 经典转 dfn 然后区间最大最小 dfn 的 LCA 即可。写了个欧拉序LCA，先写个三重循环 O(qn^2)。过样例了，确认自己没理解错题意。然后再上两个 ST 表，得到一个 O(q\cdot (len-k+1)) 的算法。这样就有 32pts 了。

此时 9:45，在搞 T3 和 T4 之间犹豫了一下，还是决定搞 T4，因为 T4 的链感觉比 T3 的神秘 DP 更可做一点。

在草稿纸上手玩了几个例子，链就是区间长度 k 的 min 的 max。想到这里感觉搞个线段树啥的，但是好像怎么做都是 O(qn) 的。苦思冥想，发现居然 10:30 了？赶紧滚回去看 T3。

看 T3。

欸？这不是把边的树建出来然后换根就完事了吗？
哦，原来边建出来不是树，而是团树啊。

然后就卡在团树这一步卡了 30min，回过神来已经 11:00 了，感觉啥都没做。赶紧去上厕所清醒一下。

回来想到建立虚点然后向团里的所有点连边，边的数量回到 O(n)。在纸上玩了一下这个新树，对于 k=1 的只要做个简单 DP 就可以了。实点就是儿子方案数乘积，虚点额外乘一个阶乘即可。10min 写完过了样例四，而且只跑了 0.5s，感觉很稳。又多了 24pts。

同时点开所有大样例，发现有一个全输出 1. 一看是 sub18，一想确实是 1，于是多了 4pts。

再想了菊花，\sum (n-2)!-(i-1)\cdot (n-3)! 即可。于是多了 12pts。

此时 T3 拿了 40pts，比较满足。想了 k=2 怎么去重，发现不会。往后看 T3 其他点，发现全都不会而且没有思路。于是放弃 T3 的神秘 DP，转而去想 T4 的神秘线段树。

注意到 T4 没有强制在线，所以考虑离线。但是发现询问按 l,r,k 排序都不可做。已经 11:30 了，感觉 T4 这种板 DS 题同学都秒切了，有点压力。于是上厕所。

回来想 T4。子段 min 的 max 显然考虑二分，二分之后判断是否有连续的长度 \ge k 的子段。但是二分判断的复杂度都 O(n\log n) 了，总复杂度 O(qn\log n) 反向优化。卡在这里 10min。上个厕所冷静一下。

然后就想到整体二分（伏笔回收）。感觉很对，20min 写了，一遍过大样例。然而 1e5 的跑了 1.1s，自造极限数据跑了 7s。加了快读和一些优化，丢了，回去想 T3。运气好 64pts，运气不好 52pts。总之有概率上 300，也算是达成教练定的目标了。

12:30 的时候判断自己想不出来了。开始检查。查了一遍没问题，双手离开键盘。

估分 100+100+40+52/64 = 292/304。

赛后

问 rlc，他也是 304。bamboo 则是 232 + ?。感觉这个 ? 很有潜力。nuclear_pasta 怎么 T3 过了 T1 没过啊，这么神秘。

周围一圈好像我和 rlc 最高？？？

下了五层楼想起来文件袋没拿，飞奔回去。

拿了文件袋回来，rlc 说自己 T4 的 A 性质好像假了，直接求的区间第 k 小过大样例了？？？

但是区间第 k 小显然不对吧。但是过大样例了。但是这什么东西啊。

反正考完了不管了。

去边上的公园玩、打牌。bamboo 使用奶龙之力大获全胜。

三点多回家了。