CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== 团队 =====

2020.08.03 [[2020-nowcoder-multi-8|2020牛客暑期多校训练营（第八场）]] ''pro: 5/7/11'' ''rk: 10/685''

2020.08.01 [[2020-nowcoder-multi-7|2020牛客暑期多校训练营（第七场）]] ''pro: 8/8/10'' ''rk: 5/1090''

===== 个人 =====

==== zzh ====


=== 专题 ===


=== 比赛 ===


=== 题目 ===

==== pmxm ====


=== 专题 ===


=== 比赛 ===


=== 题目 ===

==== jsh ====


=== 专题 ===


=== 比赛 ===


  * 2020/07/31 [[https://yukicoder.me/contests/274|yukicoder contest 259]] ''problems: 5/6/7''
  * 2020/08/02 [[https://atcoder.jp/contests/abc174|AtCoder Beginner Contest 174]] ''problems: 6/6/6''
  * 2020/08/05 [[https://codeforces.com/contest/1399|Codeforces Round #661 (Div. 3)]] ''problems: 6/7/7''

=== 题目 ===

===== 本周推荐 =====

==== zzh ====

[[url|Link]]

**Tags**：

**题意**：

**题解**：

**Comment**：

==== pmxm ====

[[url|Link]]

**Tags**：

**题意**：

**题解**：

**Comment**：

==== jsh ====

[[https://yukicoder.me/problems/no/1143|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**：没见过的科技，但是也确实应当可以自己来构造一下，有点菜。
CVBB ACM Team

用户工具

站点工具

页面工具
