勵志用盡量少的代碼做高效的表達。

---

提交（題目）鏈接→UVa-679

---

題目大意：

有一顆滿二叉樹，每個節點是一個開關，初始全是關閉的，小球從頂點落下，如果開關打開，則落向該節點的右子樹，如果開關關閉，則落向該節點的左子樹。小球每次經過開關就會把它的狀態置反，問第k個球下落到d層時經過的開關編號。

思路分析；

最初的想法是：使用一維數組模擬樹的遍歷。

因為題目比較簡單，就沒有估算時間復雜度。 寫出來后提交，顯示TLE。
于是結合紫書自己分析了一下：
因為I的取值可以最大為2^21-1,而最大深度為20，因此一組數據的計算量就高達1000W。而一共可能有10000組數據。 因此常規方法一定會超時。
仔細看了解析，敲出了優化方法。

優化的想法是：規律推導+數學公式實現。

因為每一個小球都會落到根節點上，因此前兩個小球必然是一個在左子樹的最左側，一個在右子樹的最左側。
因此可得：只需看小球的奇偶性，就能知道他是最終在哪棵子樹。
同理：對于那些落入根節點左子樹的小球來說，只需知道該小球是第幾個落在根的左子樹里的，就可以知道下一步是往左還是往右了。
如果使用題目中給出的編號I，則當I是奇數時，它是往左走的第(I+1)/2個小球，當I是偶數時，它是往右走的第I/2個小球。 可以直接模擬最后一個小球的路線：
這樣程序的運算量就與小球編號無關了，而且節省了一個巨大的數組。
（PS：敲到這里，偶然想起從前做過的一道題：大致是求1-n的連加和。如果直接遍歷，值會溢出。 最后采用高斯公式：sum = n(n-1)/2解決問題。 規律果然都是相通的。）*

---

下面把兩種代碼都貼出來，供學習參考。

超時的代碼：

#include<stdio.h> #include<cstring> const int maxd = 20; int s[1<<maxd]; int main() {int n; scanf("%d", &n); while(n--) {int D, I; scanf("%d %d", &D, &I); {memset(s, 0, sizeof(s)); //a數組從1開始運算 int k, n1 = (1<<D)-1;for(int i = 0; i < I; i++) { //遍歷小球 k = 1;for(;;) {s[k] = !s[k];k = s[k] ? k*2 : k*2+1;if(k > n1) break;}}printf("%d\n", k/2);}}return 0; }

AC代碼：

#include<stdio.h> int main() {int n; scanf("%d", &n); while(n--) {int D, I; scanf("%d %d", &D, &I);int k = 1;for(int i = 0; i < D-1; i++) if(I%2) { k *= 2; I = (I+1)/2; }else { k = (k*2+1); I /= 2; }printf("%d\n", k);} return 0; }

收獲：

1、對樹遍歷的模擬
2、規律推導+數學公式的實現。

---

擇苦而安，擇做而樂；虛擬現實終究比不過真實精彩之萬一。

總結

以上是生活随笔為你收集整理的12行代码AC——例题6-6 小球下落(Droppint Balls, UVa 679)——解题报告的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。