CSP-S 2026 游记
赛前
比赛当天上午摇出
link
赛时
t1：0s秒出，两遍过大样例
t2：蛙趣这题面写的一坨什么东西，哦n<=500啊直接Floyd再搞点东西做完了，怎么没过大样例，哦4个int相加没转long long爆了，改改过了
t3：一开始看错题面了，以为最短路径指的是距离最短的路径，然后不出意外的秒了，不出意外的20min写完了，然后没过大样例，手模小样例后发现自己看错题了，然后开始顺推
首先注意到了如果两个点之间恰有两条最短路那么必然是从前往后贪和从后往前贪，和任何时候往反方向走就不可能是最短路了，然后发现恰有两条路径等价于上述两条路径恰有一个点不同并且不同的那两个点距离为1，根据这个写了个三次方过大样例了，并把刚才的东西严谨证明了一遍
然后发现向左贪向右贪可以分别建成两棵树，可以枚举两个距离为1的点，那么除两个端点外的路径在两棵树上都是一直往上的一条路径，在树上跳一跳即可做到n乘树高，调一调过n很小的大样例了
然后一看这东西，这不就是前缀和状物吗，改一下过所有大样例了，最大点0.6s，好慌qwq
t4：枚举两个连通块最近的两个点直接贪可以做到 O(n^3)，拿到30pts，之后拼尽全力无法想出50pts
赛后
出考场后问问题环节
我问别人的时候：你是不是过t3了
别人问我的时候：你是不是AK了
吓哭了，全世界都秒t3了，全世界都说t3是水题，还有一小车人会t4 50+的，我还能去WC吗/kel
得分：100+[0,100]+[0,100]+30，平均230pts，被学弟单调队列了/ll