原题链接：https://vjudge.net/problem/UVA-12166 分类：树 备注：二叉树，思维技巧
完全没有思路，看了一些题解的描述和部分代码就顿悟了，因为至少一个不修改，而这一个不修改就足以控制全局，得到最大的根值为 定值*pow(2,深度)，如果不止一个秤砣定值能得到同样的最大根值，则这些秤砣都可以不变。找出最多的不变数即可。
在某处看到一个总结：找每个元素的某个贡献值的大小，同时统计该贡献值下元素有几个，那么最后取得最优值即可，这是竞赛中的常见思维。
代码如下：
#include<string> #include<iostream> #include<algorithm> #include<map> using namespace std; typedef long long ll; int t; ll sum; string s; map<ll, ll>vis; void balance(int L, int R, int depth) { int p = 0; if (s[L] == '[') { for (int i = L + 1; i <= R; i++) { if (s[i] == '[')p++; if (s[i] == ']')p--; if (s[i] == ',' && p == 0) { balance(L + 1, i - 1, depth + 1); balance(i + 1, R - 1, depth + 1); } } } else { ll w = 0; for (int i = L; i <= R; i++) w = w * 10 + s[i] - '0'; sum++; vis[w << depth]++; } } int main(void) { cin >> t; while (t--) { sum = 0; vis.clear(); cin >> s; balance(0, s.length() - 1, 0); ll ans = 0; for (auto it = vis.begin(); it != vis.end(); ++it) ans = max(ans, it->second); cout << sum - ans << endl; } return 0; }