UVa 12166 Equilibrium Mobile——思路题

UVa 12166 Equilibrium Mobile——思路题

由平衡可知父节点的质量等于子节点的两倍，某层的质量等于他下面一层质量的两倍，最终第0层的质量就是整棵树的质量（这里的质量其实类似于一种权值的累加，不是实际质量，不要误以为是所有叶子质量之和。。。。。。）

以1片叶子为基点，则1片叶子就可以决定1棵树的质量；

以n片叶子为基点，则n片叶子就可以决定n棵树的质量；

如果n棵树中有两棵树的质量相同，则作为他们基点的两片叶子是不用修改的； 如果n棵树中有三棵树质量相同，则作为他们基点的三片叶子是不用修改的。。。。。。

如果n棵树中有m棵树质量相同，则作为他们基点的m片叶子是不用修改的。

最终需要修改的叶子就为n-m片

#include using namespace std;int main(){ string s; map m; map::iterator it; int T; cin >> T; while (T--) { cin >> s; m.clear(); int deep = 0, a = 0, b = 0; for (int i = 0; i < s.size(); i++) { if (s[i] == '[') deep++; else if (s[i] == ']') deep--; else if (isdigit(s[i])) { a++; long long sum = 0; while (isdigit(s[i])) { sum = sum * 10 + s[i++] - '0'; } sum = sum * (1<second); cout << a - b << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。