NOIP 2024 游寄

总结：季风，贯穿全文的线索/qd

蒟蒻的最后一次NOIP 2024游记 /hsh

11.28 Day -1

计划写一下季风

实际：摆烂

11.29 Day 0

上午计划补一下季风

实际：摆烂

下午 14:00 从学校出发，坐高铁去考点。

17:30 到酒店，发现kfc没有外卖，遂打车去线下 然鹅最后吃的是火锅

20:30 吃完饭回酒店，计划写一下季风。实际：摆烂，找人面积；面到了@TLEWA，遂一起摆烂，与@TLEWA @zaochen @muqi132一起去 @murder_drones 房间开impart玩你画我猜，最终被酒店的垃圾wifi和gzzx教练打断施法。

回自己房间继续开摆。

11.30 Day 1

早上很早就醒了，继续睡，被闹钟叫醒。

吃完早饭打车去考点。

7:40 进考场，写个缺省源，写完开始睡大觉。

8:10 测试数据开放下载。大概是因为CSP-S的网络问题被扣钱扣怕了吧/qd 简单看了一下样例，没发现什么特别的，遂继续睡大觉。

8:30 开考，下载题面，开T1。第一眼感觉不是很可做，又看了两眼发现直接贪心就行了。写写写，欸怎么过不了样例 wc没看到相邻/tuu 白写45min 但是贪心的思路很对，分个段继续贪就行了。写写写，过完大样例直接扔了

9:30 开T2，第一眼不会，再看一眼发现方案很好构造，简单推了下柿子，这不是若只数学题吗，写写写，15min过大样例，直接扔。

中间去上了个厕所。

10:00 开T3，一眼看成对k条边分别求解，写写写，发现要算总方案数，感觉是个神秘容斥，不会 先跳了。

10:30 开T4，一眼注意到区间只能选长度 k 的，结合一下dfs序求多点lca就变成RMQ问题了，很快就搓出来了个 O(n\log n+\sum k) 的做法，32pts。

接下来的过程就很折磨了，对于每个左端点，注意到随右端点的增大 lca深度只会减小 满足单调性，可以写个整体二分，但是感觉需要很多个 \log，遂先回去写T3 k=1 特殊性质。

11:20 开写T3特殊性质，把边提出来对两棵树做一下树形dp就行了，很快就过了对应的样例，24pts

11:40 回去写T4的整体二分，发现右端点不太好用双指针，只得再套个二分，算上lca的 \log，整体的复杂度达到了恐怖的 O(n\log^3n)，大概是过不了最大的样例的，但是还是只能硬着头皮写。

12:10 写完了T4整体二分，发现过不了样例，试着调整了一下二分边界就过了。然而跑 10^5 样例时仍然慢的出奇，10s 都没跑完，心态有点崩。（场上忘记O(1) lca了）

12:30 感觉写不动了，开始检查代码。T4权衡了一下还是交了 O(n\log n+\sum k) 的做法，把整体二分注释之后扔代码前面了。

12:40 提交代码，然而机器死机了/px 还好代码重启之后还在 什么垃圾机器/fn/fn/fn（只有6G内存不容易死机才怪）

13:00 提交，出场。

赛后问了一圈，感觉不少人卡在T1 or T2上了。

15:30 坐高铁回家

16:30 到站，和@zaochen一起挤地铁。到家，继续开摆。

欸我季风怎么还没写/qd

赛后发现T2判无解没读完，而且又过了大样例，彻底裂开了

估分 100+[35,100]+24+32=[191,256]。

不知道是不是要退役了/kk

upd：\sum k 指的实际上是 \sum (r-l+1-k) /qd

upd：T2没挂，CCF数据魅力时刻

final：100+100+24+32=256