CSP-S2026 游记

DAY -3

校内信心赛，怎么还要和初三的学弟一起打，T1发现一个双指针就做完了，像是NOIP2024 T1 的超级弱化版。T2 有点像一个离线二维数点，岛屿之间的低谷如果也在海平面之上那么相邻两个岛屿就是可以合并的，直接写了一发，怎么大样例过不去？？？，好像错误的答案只差1，原来一些询问，可能会将一个岛屿拆成两部分，这两部分都是合法的，那么答案计数会少1，把这点特判一下好像就过了，T3看了一下本来不会，但是怎么 \(n^2\) +特殊性质竟然就有80分，这个只用了大概20分钟就敲完了，（此时我还不知道 T3 的正解比他更短），然后就是看 T4 ，n<=3000的数据让我一眼就想到了树上背包，但还是不怎么会，为保险起见，敲了一个n<=18的指数级暴力，接着就是开始推式子写AB性质，出分 100+100+80+40=320 分，T4 的 B性质因为没清空G了。T3原来 bfs 一下就对了，T4 的树上背包暴露出来的我的问题，于是决定明天多写一些这样的题。

DAY -2 ~ DAY -1

好像现在没有什么特殊的安排了，于是就是狂敲CSP-S 的模板，和随机写题，重点写了一些树上背包的习题，感觉考前只要有人有做不出来的题就会引得全机房焦虑，所以到了周四晚上就没再写了，回顾了一下这一个月的模拟赛情况。

DAY 0

上午因为大家都没有在写新的难题了，气氛明显欢快了一些，然后就是大扫除，做完这些吃个饭就基本要出发了，到达郑州看了后严肃和 zwq 下了两盘国际象棋，本来第一盘 zwq 就只剩下一个王了，怎么下完一步后屏幕上突然显示和棋，听完 zwq 的讲解才知道和棋规则，气煞我也，第二盘直接速通获胜，后面就是下楼去吃了个米线，感觉味道还不错，然后就是和 zwq 玩抓薯片机，我抓了两个，zwq 抓了滚木，晚上和 lzf ,zwq,一起玩了会电脑，坦克动荡 zwq 被虐穿了，没有敢睡特别晚，毕竟还得以明天考试为主。

DAY 1

上午好像一直在颓，就是到中午的时候边吃烧肉饭边看了看 J 组的题目难度，J 组难度是红橙黄绿，S组会不会是青蓝紫黑呢？？？ 去比赛的路上发现忘拿水了，询问kakaship，他直接热心的把自己的水溶C给我了，感谢感谢。

快进至考场

2：20——2：35

电脑刚开启，扫视了桌面半天没找到DEV，打开D盘，空空如也，等了5分钟才发现放到C盘文件里了，等到安装好，敲完包子皮编译后发现程序运行这么慢，不对，已经开考5分钟了，出师不利呀！！

2：35——2：55

开T1，发现只有+1的操作，那么就是一个双指针的事情吗，比去年的T1简单多了，8分钟敲完，这个大样例好麻烦，怎么跑起来这么慢，输出了一下时间，原来是环境需要缓冲一下，跟代码没什么关系，2：55 分通过T1 所有大样例

2：55——3：35

开T2，光对题意的理解就已经花了10分钟了，推了推样例，原来地铁是可以双向移动的，注意到 \(n \le 500\) ,并且题目中给了一个重要性质，每个地铁站所属的地铁数量不超过20，那么我们直接把每个地铁线看成点，站点的换乘看成边，跑 floyd 就行了，敲完发现一遍过小样例，又一遍过大样例，有点慌，不会样例水吧，此时是 3：35，不管了，先往后做。

3：40——5：50

这 两个小时堪称最区的时间，本来想着要尝试着磕T3正解，首先我们预处理出来每一个节点最左边能一部达到的点和最右边能一步达到的点，然后紧接着观察到了本题比较重要的一个性质，从左端点尽量往右跳，和从右端点尽量往左跳，他们两条路径最多只有一个位置不同，难道要暴力枚举不同的位置吗？ 到这里好像突然就宕机了，以为这样写是 \(O(n^3)\) 的，还不是很好做，然后就又推了推方案数两种情况的构造方式，此时似乎我已经发现不同的位置他们是紧紧相邻了，但并没有和前面想的结合到一块，（区呀），于是就先敲了一个假算，这个假算甚至通过了 T3 的小样例，赛后发现这个假算是能过 B 性质的，然后又推了推 A 性质，此时都5：20了，我胡了一个暴力建边+topsort 的假 \(n^2\) 算法，通过了 n<=300 的大样例。赛后发现边数其实是 \(O(n^2)\) 的，所以整体复杂度最坏可以到达 \(O(n^3)\) ,期望得分 40分。

5：50——6：30

然后就开了T4，这种最大值最小一般都是要考虑二分答案的，但我也没有什么心思去想正解了，直接火速 \(2^n\) 拿下15分。

期望得分 100+100+40+15=255，希望别挂分

结束后，发现同机房的人基本上都是200+ 了，Air 甚至达到了340+ %%%