CVBB ACM Team

2020.08.03 2020牛客暑期多校训练营（第八场） pro: 5/7/11 rk: 10/685

2020.08.01 2020牛客暑期多校训练营（第七场） pro: 8/8/10 rk: 5/1090

• 2020/07/31 yukicoder contest 259 problems: 5/6/7
• 2020/08/02 AtCoder Beginner Contest 174 problems: 6/6/6
• 2020/08/05 Codeforces Round #661 (Div. 3) problems: 6/7/7

Link

Tags：

题意：

题解：

Comment：

Link

Tags：

题意：

题解：

Comment：

yukicoder - No.1143 面積Nの三角形

Tags：海伦公式，Ravi 变换

题意：求面积恰好为 $n$、各边均为正整数的三角形有多少个（全等的记为同一个）。

题解：

首先，若三边为 $a, b, c$ 的三角形面积为 $n$ 有海伦公式： $$n^2 = s (s - a) (s - b) (s - c)$$ 其中 $2 s = a + b + c$。

这时可能就没什么好头绪了，因为枚举 $a, b$ 后，即不容易解出 $c$，也还需要额外判一次合法性。同时复杂度也没有保障。

这时我们记 $x = s - a$, $y = s - b$, $z = s - c$，公式就变成了： $$n^2 = x y z (x + y + z)$$ 考虑枚举 $x, y$，发现 $z$ 只需要解一下二次方程即可，同时枚举的复杂度上界也是 $n$ 的因子数量的平方，并不大。

再考虑是否会出现不合法的解，首先容易知道一组 $x, y, z$ 的解可以确定出唯一的 $a, b, c$；同时，实际上 $2 x = b + c - a$, $2 y = a + c - b$, $2 z = a + b - c$，即只要保障 $x, y, z > 0$，就可以确定一个合法的三角形了。

上述 $a, b, c$ 与 $x, y, z$ 的变换被称作 Ravi 变换。

Comment：没见过的科技，但是也确实应当可以自己来构造一下，有点菜。