警钟……？

收录一些题目或解法方面的错误/天才想法/trick。

1.trick

1-1.切比雪夫距离和曼哈顿距离互转

切比雪夫距离

d_2=\max(|x_1-x_2|, |y_1-y_2|)

，曼哈顿距离

d_1=|x_1-x_2|+|y_1-y_2|

。

2\times\max(a,b)=a+b+|a-b|\\ (a,b\geqslant 0)\Rightarrow (a+b=|a+b|)\\[10pt] \Big||a|+|b|\Big|=\begin{cases}|a+b|,ab\geqslant0\\|a-b|,ab<0\end{cases}\\ \Big||a|-|b|\Big|=\begin{cases}|a-b|,ab\geqslant0\\|a+b|,ab<0\end{cases}\\ \therefore \Big||a|+|b|\Big|+\Big||a|-|b|\Big|=|a+b|+|a-b| \\[10pt] \begin{aligned}%align 会出现 (1)(2)(3) 号 &d_2\Big((x_1,y_1),(x_2,y_2)\Big)\\ =&\max(|x_1-x_2|, |y_1-y_2|)\\ =& \dfrac{\Big||x_1-x_2|+|y_1-y_2|\Big|+\Big||x_1-x_2|-|y_1-y_2|\Big|}2\\ =& \dfrac{|(x_1-x_2)+(y_1-y_2)|+|(x_1-x_2)-(y_1-y_2)|}2\\ =&\dfrac{|(x_1+y_1)-(x_2+y_2)|+|(x_1-y_1)-(x_2-y_2)|}2\\ =&\dfrac{d_1\Big((x_1+y_1,x_1-y_1),(x_2+y_2,x_2-y_2)\Big)}2\\ =&d_1\left((\dfrac{x_1+y_1}2,\dfrac{x_1-y_1}2),(\dfrac{x_2+y_2}2,\dfrac{x_2-y_2}2)\right) \end{aligned}

同理换元（令

a=x+y,b=x-y

）可得

d_1\Big((x_1,y_1),(x_2,y_2)\Big)=d_2\Big((x_1+y_1,x_1-y_1),(x_2+y_2,x_2-y_2)\Big)

。（注意

x\gets x+y,y\gets x-y

的时候切比雪夫距离转曼哈顿距离需要除以

2

，而曼哈顿距离转切比雪夫距离的时候不需要。）

三维空间切比雪夫距离和曼哈顿距离不能直接互转，因为曼哈顿是八面体（

6

个顶点）而切比雪夫是正方体（

8

个顶点）。但是如果保证两点都在

x+y+z=C

平面上，两点间曼哈顿距离恰好等于其切比雪夫距离的

2

倍。遇到六边形最短距离的时候可以往这方面想，例题：2025 hdu 多校#7 1002 龙族栖息地。

1-2. 旋转坐标系 45 度

$y_i + d \geqslant |x_i-x_j| + y_j\Rightarrow\\ \begin{cases}y_i+d\geqslant x_i-x_j+y_j\Rightarrow(y_i-x_i)+d\geqslant (y_j-x_j)\\ y_i+d\geqslant -x_i+x_j+y_j\Rightarrow (y_i+x_i)+d\geqslant(y_j+x_j)\end{cases}\\ \text{i.e. }x'_i+d\geqslant x'_j,\ y'_i+d\geqslant y'_j.$ —— 「NAPC #2」rStage3 ~ Hard Jump Refreshers

1-3. 拆绝对值

比如我们有

dp_i\gets\max_{j<i}(dp_{j-1}+|a_i-a_j|)

，因为

|x|\geqslant \pm x

且

\max(x,-x)=|x|

，那么可以直接把转移方程写成

\\dp_i\gets \max_{j<i}(dp_{j-1}+(a_i-a_j))=a_i+\max_{j<i}(dp_{j-1}-a_j),\\ dp_i\gets \max_{j<i}(dp_{j-1}+(a_j-a_i))=-a_i+\max_{j<i}(dp_{j-1}+a_j)

，这样分别维护

dp_{i-1}\pm a_i

的前缀最大值就能

O(n)

做完了。（当然如果原方程改成

\min

就要求绝对值前面是负号，否则把

|x|

拆成

\pm x

就会产生增根。）

2.经典模型

2-1. 六边形平面上的最短距离（见 1-1）

2-2. 正权图求最长路

如果都是正权边且最长路不是正无穷，一定不存在环，可以直接使用拓扑排序解决。

否则仍然可以拓扑排序，然后没被访问到的节点都是正无穷，因为他们在环里面或环后面。

如果边权有正有负那只能 spfa 了。

—— https://www.luogu.com.cn/discuss/907199

3.常见错误

（组合）把 $x_1 + x_2 + \dots + x_n \leqslant m$ 解个数问题和 $= m$ 解个数问题的答案搞混了，前者是后者对于 $i = 0 \to m$ 求和也就是 $\sum \binom{n - 1 + i}{n - 1} = \binom{n + m}n$ 。
在有负环的图上跑 SPFA 的时候 dis 记得开 ll，如果边权是 $10^9$ 量级的话负环跑几圈就爆 int 了。

文章操作