Warning: session_start(): open(/tmp/sess_3b9808363f1d5379bc11e3202f88881b, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
===== 团队 =====
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**:没见过的科技,但是也确实应当可以自己来构造一下,有点菜。