哪里找专业做网站的人常熟,网站建设 的系统公式,哪些网站可以找到做跨境电商的公司,wordpress圆角插件汉化问题描述
天平的两边有时不一定只能挂物品#xff0c;还可以继续挂着另一个天平#xff0c;现在给你一些天平的情况和他们之间的连接关系#xff0c;要求使得所有天平都能平衡所需物品的总重量最轻。
一个天平平衡当且仅当“左端点的重量 \times 左端点到支点的距离 …问题描述
天平的两边有时不一定只能挂物品还可以继续挂着另一个天平现在给你一些天平的情况和他们之间的连接关系要求使得所有天平都能平衡所需物品的总重量最轻。
一个天平平衡当且仅当“左端点的重量 × \times × 左端点到支点的距离 右端点的重量 × \times × 右端点到支点的距离。 输入格式
第一行包含一个 N ( N ≤ 100 ) N(N \le 100) N(N≤100)表示天平的数量天平编号为 1 1 1 到 N N N。
接下来包含 N N N 行描述天平的情况每行 4 4 4 个整数 P , Q , R , B P,Q,R,B P,Q,R,B P P P 和 Q Q Q 表示横杆上支点到左边的长度与到右边的距离的比例为 P : Q P:Q P:Q R R R 表示左边悬挂的情况如果 R 0 R 0 R0 说明悬挂的物品否则表示左边悬挂的是天平 R R R B B B 表示右边的悬挂情况如果 B 0 B 0 B0 表示右边悬挂的是物品否则右边悬挂着天平 B B B。
对于所有的输入保证 W × L ≤ 2 31 W \times L \le 2^{31} W×L≤231其中 W W W 为最轻的物品重量而 L L L 为输入中描述左右比例时出现的最大值。
输出格式
输出一个整数表示使得所有天平都平衡所需最轻的物品总重量。
样例
样例输入1
4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0样例输出1
40数据范围
对于所有数据 N ≤ 100 , W × L 2 31 N \le 100,W \times L 2^{31} N≤100,W×L231。
题解
考虑第 i i i 个天平假设左右最轻重量为 W 1 , W 2 W1, W2 W1,W2比例为 L 1 : L 2 L1:L2 L1:L2当前需要左右放 X X X 和 Y Y Y。 则 X X X 和 Y Y Y 需要满足 W 1 × L 1 × X W 2 × L 2 × Y W1 \times L1 \times X W2 \times L2 \times Y W1×L1×XW2×L2×Y。 移项可得 X Y W 2 × L 2 W 1 × L 1 \frac{X}{Y} \frac{W2 \times L2}{W1 \times L1} YXW1×L1W2×L2。 因此天平重量最小必须将 x y \frac{x}{y} yx 化为最简分数。 求出 W 2 × L 2 W2 \times L2 W2×L2 和 W 1 × L 1 W1 \times L1 W1×L1 的最大公因数 P P P X W 2 × L 2 × P X W2 \times L2 \times P XW2×L2×P Y W 1 × L 1 × P Y W1 \times L1 \times P YW1×L1×P。 重量为 X × W 1 Y × W 2 X \times W1 Y \times W2 X×W1Y×W2。 处理时直接递归求解
#define int long long
int dfs(int x){if(x 0){//边界return 1;}int t1 dfs(l[x]), t2 dfs(r[x]);int t __gcd(a[x] * t1, b[x] * t2);return t1 * a[x] * t2 / t t2 * b[x] * t1 / t;
}
signed main(){scanf(%d, n);for(int i 1; i n; i){scanf(%d %d %d %d, a[i], b[i], l[i], r[i]);f[l[i]] 1;f[r[i]] 1;}int rt 0;for(int i 1; i n; i){if(!f[i]){rt i;break;}}printf(%lld, dfs(rt));return 0;
}
