大东北是我的家乡~

· · 生活·游记

标题来源于CSP-S2026HN考场某考生手机铃声。

考前一天通刷了一下板子，感觉没啥能考的了，就是贪心最短路DP和一个不明题目。没想到完美压中。

14：00进入考场，发现有vscode用开心！结果无法编译 g++ 命令行直接被迫使用DEV……

14：30拿到解压密码，万圣节老梗了。

开 $T_{2}$，上来直接将线路压成点跑 `dijkstra`，发现 $n,m$ 看反了时间不对，不过立马反应过来这是 `floyd` 的数据范围，又看到谜之 $d$，立刻就找出一个时间比较极限的 $\mathcal{O}(n^3+md^2+qd^2)$ 做法，赛后才发现是 $\mathcal{O}(n^3+d\sum k_{i}+qd^2)$。不过赛时本地跑了 $1.5$ 秒有点慌啊，赛后复现代码交洛谷 $300ms$……此时时间 $15:10$。 开 $T_{3}$，是个计数题，此时我感觉分数线已经有了，不过发现 $T_{3}$ 似乎可做，先去看一眼 $T_{4}$ 发现好像也不抽象，剩下的时间可以慢慢做了。 首先考虑两条路径自然只有一个点不同，且两点相邻，那么考虑枚举这个不同点——的后面一个点 $X$，自然想到 $X$ 分为在末尾和在中间两种情况，那么考虑剩余路径走的都是极限，先考虑双指针算出每个点往左和往右的极限，这里记作 $f_{i,0/1}$。 然后考虑借助这两个东西维护断点前的路径数量和断点后的路径数量，正反两次 $dp$。 考虑前半段，首先自己会贡献 $dp_{i,0}=1$。每个点 $i$ 都可以给 $f_{i,1}$ 贡献 $1$ 的路径次数，但若 $f_{i-1,1}$ 与 $f_{i,1}$ 不同是，则 $dp_{i,0}$ 同样可以转移给 $dp_{f_{i,1},0}$，但这里有点问题，稍后来修复。 考虑后段，一个没法往右扩展的点显然 $dp_{i,1}=1$。其他的每个点 $i$ 都可以从 $dp_{f_{i,1},1}$ 转移而来，再加上自己到极限之间的点数减去 $i-1$ 到其极限的点数，因为这些点被前面点到达路径至少有两条。 考虑处理完这些，考虑看看 $f_{i,0}$ 以及 $f_{i,0}+1$ 两点作为断点的，那么答案就会加上 $(dp_{f_{i,0},0}-1)\cdot dp_{i,1}$，也就是不已$f_{i,0}+1$ 作为起点的一直跳极限到 $f_{i,0}$ 的路径数量乘上 $i$ 从 $i$ 到 $j$ 最短路唯一的 $j$ 个数。 写完后发现总是在第三个样例和第四个样例间来回挂，发现 $dp_{f_{i,0},0}$ 的计算有问题，因为有些点可以在前面不跳极限最后等价步数跳到$f_{i,0}$ 导致路径数大于 $2$，这种情况只会出现在第一个 $f_{j,1}=f_{i,0}+1$ 的 $j$ 上，考虑转移时顺手维护这个 $j$，如果 $f_{j-1,1}=f_{i,0}$ 则去掉 $j$ 以前起点给的贡献，也就是 $dp_{j,0}-1$，式子就变成 $(dp_{f_{i,0},0}-dp_{j,0})\cdot dp_{i,1}$。 没想到竟然过了大样例！此时时间 $17:25$。我当时以及兴奋的手舞足蹈了~~~ 最后思考了下 $T_{4}$，没什么高级的做法，写了 $15$ 分去检查代码去了。 预估 $100+100+100+15=315$，属实超常发挥了。 果然我的心态决定我的分数，而剩余时间决定我的挂分程度，希望分数不要再挂了qwq~