2025/8/2校CSP-S模拟赛有感（附题目解析）

我感觉我要完蛋了（whk 和 OI 一起死掉 X_X）。

预期 PTS：100 + 10 + 60 + 30 = 200

实际 PTS：100 + 0 + 10 + 30 = 140

（有个笨笨 T2 没重置变量，T3 没清理代码导致特殊解判断写错了痛失 (10 + 50) PTS 我不说他是谁）

T1 没什么好说的，注意到满足条件的数是一段连续的区间，于是可以用等差数列求和。由于每一位只有第一次操作有意义，于是令 $y$ 取 $\min(x,y)$。经过观察，满足条件的区间为 $[\underbrace{44\cdots4}{y-1}5\underbrace{00\cdots0},10^{x} - 1]$，经过计算可得：

$$ \begin{aligned} \underbrace{44\cdots4}{y-1}5\underbrace{00\cdots0} &= \underbrace{44\cdots4}{y-1}5 \cdot10^{x - y}\ &=(\underbrace{44\cdots4} + 5)\cdot10^{x-y}\ &=(4\cdot\underbrace{11\cdots1}_{y-1} + 5)\cdot10^{x-y}\ &=[4\cdot(10^{1}+10^{2}+\cdots+10^{y-1})+5]\cdot10^{x-y} \end{aligned} $$

预处理出 $10^{n}$ 以及他的前缀和，再处理 $2$ 模 $998244353$ 意义下的乘法逆元就好了。

T2 还没写出来，先不写 QAQ。

T3 是一个比较 tricky 的建图（当然可能是我太蒻了做不出来），考虑对于每个点 $u$ 建立两个辅助节点 $u_{x},u_{y}$ 作为对应该点横纵坐标的虚拟节点，并将每个节点向两个辅助节点连接零边权的边。

将平面上的所有点按照横坐标排序，接着将排序后相邻的节点 $u_{i}$ 和 $u_{i + 1}$ 对应的辅助节点连边权为 $\vert x_{u_{i}} - x_{u_{i + 1}} \vert$的双向边，同理，按照纵坐标排序，进行一次相同的操作，最后在图上跑最短路就好了。

以下使用自然语言论述该方法的正确性：

首先，我们论证按坐标排序后对相邻点建边的正确性：不妨设一组点 ${u_{1},u_{2}\cdots u_{n}}$，满足 $x_{u_{1}} \le x_{u_{2}} \le \cdots \le x_{u_{n}}$，在相邻的点间建边，不难证明通过横坐标直接在任意两点间移动的代价和通过这两点间的每一个点逐步移动的代价是相等的，纵坐标同理，此处不列出证明。

由题意两点之间的距离 $D(u,v) = \min(\vert x_{u}-x_{v} \vert,\vert y_{u}-y_{v} \vert)$,依照上文方法建图后对于任意两个点，在不经过其他点的情况下，最短路算法可以计算出这两点的距离。

于是，上文建图的方法等价于在每个点对之间直接连边，于是在该图中运行最短路算法就可以计算出两点间的最短距离，其中点数和边数规模同级。

代码实现方面，我们将存图、存距离以及标记之类的数组开三倍空间，写一个 Dijkstra 版子（真的不是在打广告）即可通过此题。

T4 太难了，有空再写（逃）