会很杂,尽量分类,每个trick会配题。
难以分类的
难以分类可能只是自己太菜了。
曼哈顿距离与切比雪夫距离的转化
对于两点\((x_1,y_1),(x_2,y_2)\),曼哈顿距离为\(|x_1-x_2|+|y_1+y_2|\),切比雪夫距离为\(\max(|x_1-x_2|,|y_1-y_2|)\)。
画图可以发现到原点的曼哈顿距离为\(1\)的点形成一个对角线在坐标轴上的正方形,切比雪夫距离为\(1\)的点形成一个边与坐标轴平行的正方形。且后一个正方形的边长为前一个的\(\sqrt 2\)倍。
我们可以想到二者可以相互转化。
大力推一下:
\[\begin{aligned} |x_1-x_2|+|y_1-y_2|&=\max\{(x_1-x_2)+(y_1-y_2),(x_2-x_1)+(y_1-y_2),(x_1-x_2)+(y_2-y_1),(x_2-x_1)+(y_2-y_1)\}\\ &=\max\{|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|\} \end{aligned} \]容易发现这就是\((x_1+y_1,x_1-y_1),(x_2+y_2,x_2-y_2)\)两点之间的切比雪夫距离。
\[\begin{aligned} \max\{|x_1-x_2|,|y_1-y_2|\}&=\max \Big\{\frac{x_1+y_1}{2}-\frac{x_2+y_2}{2}+\frac{x_1-y_1}{2}-\frac{x_2-y_2}{2}\Big\} \end{aligned} \] 标签:长期,frac,曼哈顿,max,Tricks,更新,距离,aligned,比雪夫 From: https://www.cnblogs.com/EmilyDavid/p/18446031