题目的大意是一个树形天平,输入给出样例的个数,然后空一行,每行4个数W1,D1,W2,D2,分别代表天平左侧的重量、力臂和天平右侧的重量、力臂。如果W1或者W2为0,则代表该节点有左子树或右子树,如果W1,W2同时为0,则下一行先给出左子树,再下一行给出右子树,判断输入的天平是否平衡。
仔细分析,可以发现输入的方式是递归的,因为输入的数据其实是先序遍历一棵树的结果。这样我们就可以将输入修改成递归的,根据输入的数据,进行树的递归遍历。
这里我们注意到节点的重量为0,因此我们需要将节点的重量值加上它子树的重量,才能在节点这一层进行判断,所以用引用传值。
另外,比较复杂的输入格式我们可以直接用C++的cin来简化,同时注意中间有空行的小技巧,最后一个输出后不能有空行。
话不多说,代码如下:
1 #include2 using namespace std; 3 bool solve(int &w){ //如果平衡,返回true 4 bool sub1=true,sub2=true; 5 int w1,d1,w2,d2; 6 cin>>w1>>d1>>w2>>d2; 7 if(!w1)sub1=solve(w1);//让后续的子树的重量累计到分支节点上 8 if(!w2)sub2=solve(w2); 9 w=w1+w2; //累计到分支节点上 10 return sub1 && sub2 && (w1*d1 == w2*d2);11 } 12 int main(){13 int t,w;14 cin>>t;15 while(t--){16 solve(w)?cout<<"YES\n":cout<<"NO\n";17 if(t)cout<