A. 数列

要求$ax+by=s$，使得$abs(x)+abs(y)$最小的一组解$(x，y)$。

首先用$exgcd$求出一组特解$(x_1,y_1)$。

因为$a,b$均为正数，可以将$s$转化为正数。

不妨将解$x,y$画到一个坐标系上，

显然$abs(x)+abs(y)$在$x$接近$0$或$y$接近$0$的时候取得最小值，所以分别试一下就完了。

B. 数对

当问题转化为不以任意顺序排序，显然是线段树优化$dp$。

所以应该排序后$dp$？

然而并没有找到拓扑序，于是就完戏了。

正解是将每个元组以$a+b$为基准排序。

证明可以分类讨论，

考虑每个元组对$(i,j)$，显然我们只关注二者$a$，$b$交叉的大小关系确定先后顺序。

当$a_i<b_j,b_i<a_j$，将$j$放在$i$的后面可以使这个元组对合法，反之则不行。

当$a_i>b_j,b_i>a_j$，情况类似。

当$a_i<b_j,b_i>a_j$，无论怎么放元组对都是合法的。

当$a_i>b_j,b_i<a_j$，无论怎么放元组对必死。

综上可以得出按$a_i+b_i$为基准排序的结论。

C. 最小距离

一眼二进制分组？？？

将每个二进制位下为$0$的点同时设为起点跑最短路，更新该位下为$1$的答案。

同理用$1$的点更新$0$。

然后复杂度$O(nlog^2)$，疯狂卡常，极限数据仍然要$2s$多。

改成$spfa$，假装不会被卡，极限数据本机跑了$1s$左右，

最后感觉多半是完戏了，果然被卡成50分。

正解是将所有特殊点同时设为起点，只跑一次最短路，同时记录下距离每个点最近的特殊点。

枚举每一条边，用这条边的权值加上两个连接点的$dis$更新两个特殊点的答案。

这样做的正确性似乎是显然的，然而没有想到。

当一条边更新了特殊点对$(a,b)$的答案，显然这个点对的问题是没有问题的。

如果同时存在一个点$c$，这个答案也会在其它地方被更新。