題目鏈接
題目
Mark下大神的博客：http://morris821028.github.io/ 簡直太強了。 題解鏈接：http://morris821028.github.io/2014/10/03/oj/uva/uva-12166/#PRoblem
題目大意：
給一個天平表達式，請問至少要調整幾個權重才能使之平衡。（直接復制來的）
解題過程：
自己大概廢了一個小時想一個特麻煩的解法，首先想的是自頂向下的平衡，然后dfs下去還是從必須從葉節點開始平衡。
于是想自底向上平衡，每次把可以平衡成的質量和調整的次數傳給上一層，比如調整[1,2]，給上一層傳遞三個狀態：調整2到1，質量變為1，調整1次；調整1變為2，質量變為2，調整一次；兩個都一起調整到一個任意的數，調整兩次。 顯然這樣需要給每個節點開辟一個空間儲存狀態，妥妥爆內存。
想了一個小時只是這個結果，于是去百度了下，看到： 那麼可以得知道假使一個權重不改，最後的天平重量為何。 假使 depth 上的權重 w 不改，則最後的天平重量就是 w * pow(2, depth)。
于是想到建樹，統計下葉子節點所在的層數，然后拿每個葉子節點跑一邊，結果是O(n^2)。
后來看到這個博客確實是驚艷到了……
題目分析：
這里分析下下面的代碼好了。
這里map的使用和遍歷可以做模板了，要是我的話，就桶排然后遍歷一遍了…
這個遞歸寫的真是太強了?。?/p>
然后就是sscanf的用法，可以拿來做模板，要我的話，專門寫一個字符串轉整數的函數了，麻煩的要死。
AC代碼：
#include <cstdio>#include <cstring>#include <map>using namespace std;char exp[1123456];map<long long, int> R;void dfs(int l, int r, int dep){ if (exp[l] == '[') { int p = 0; for (int i = l + 1; i <= r - 1; i++) { if (exp[i] == '[') p++; if (exp[i] == ']') p--; if (p == 0 && exp[i] == ',') { dfs(l+1, i-1, dep+1); dfs(i+1, r-1, dep+1); } } } else { int w; exp[r+1] = '/0'; sscanf(exp+l, "%d", &w); R[(long long)w<<dep]++; }}int main(){ int testcase; scanf("%d", &testcase); while (testcase--) { scanf("%s", exp); R.clear(); dfs(0,strlen(exp) - 1, 0); int sum = 0, mx = 0; for (map<long long, int>::iterator it = R.begin(); it != R.end(); it++) sum += it->second, mx = max(mx, it->second); printf("%d/n", sum - mx); } return 0;}
