警钟……？

· · 个人记录

偏实现的错误见 警钟撅烂。

收录一些题目或解法方面的错误/天才想法/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.常见错误

  1. （组合）把 x_1 + x_2 + \dots + x_n \leqslant m 解个数问题和 = m 解个数问题的答案搞混了，前者是后者对于 i = 0 \sim m 求和也就是 \sum \dbinom{n - 1 + i}{n - 1} = \dbinom{n + m}n。
  2. （组合）上指标求和时 \sum\limits_{i=0}^n\dbinom im=\dbinom{n+1}{m+1} 记得特判 m<0！\dbinom0{-1}\not=\dbinom10！
  3. （组合）x_1 + x_2 + \dots + x_n = m 解个数问题，记得特判 n=0 \land m=0，因为 \dbinom{-1}{-1}\neq\dbinom00！

  1. （模拟）旋转一个矩阵时，画图：

    然后就写出了错误代码（a为原矩阵，b为旋转后矩阵）：右旋 b[i][j] = a[j][n - i + 1];，但是这个其实是左旋。

    正确思路：枚举原矩阵下标 i/j，追踪 a[i][j] 的新位置，用原 i/j 表示是 (j, n - i + 1)，新数组新位置存原来的值 a[i][j]，所以代码是 b[j][n - i + 1] = a[i][j];。特别注意！