UVA 839
题意
给你一个天平,有砝码重量w1, w2,力臂长度d1, d2。判断天平是否平衡。砝码重量为0时,代表砝码是一个子天平,整个天平的输入按先序输入例如:
Sample Input
1
0 2 0 4
0 3 0 1
1 1 1 1
2 4 4 2
1 6 3 2
分析(此题递归有难度)
- 题目输如按先序给出,自然用递归读入,读入同时可以判断。
- 可以用较高难度的递归时引用参数,这样可以做到递归到最底层,往上回来时,可以把子天平的砝码和赋值给上一级。
代码(输出有坑,最后一个空格不能输出)
#include<bits/stdc++.h>
using namespace std;
const int N = 10000 + 10;
const int INF = 0x3f3f3f3f;
int _, w;
//由于用的是引用参数,递归的每一层都会对上一层的w 产生影响,也即计算了子树砝码的总和,递归结束后直接判断
bool solve(int& w)
{
int w1, d1, w2, d2;
bool left, right;
left = right = true;
cin >> w1 >> d1 >> w2 >> d2;
if(!w1)
left = solve(w1); //注意,递归由于用的是引用赋值,下面w1, w2的值经过调用已经改变
if(!w2)
right = solve(w2);
w = w1 + w2; #注意:这里的w是上一级的引用,不是全局变量。此时已经将当前天平砝码和赋值给上一级
return left && right && (w1 * d1 == w2 * d2); //平衡的三个条件,左天平平衡,右天平平衡,当前天平平衡
}
int main()
{
for (scanf("%d", &_); _; _--){
if(solve(w)) //每次判断一个子天平
cout << "YES" << endl;
else
cout << "NO" << endl;
if(_ != 1)
cout << endl;
}
return 0;
}