a249 - 00679 - Dropping Balls

🔗 前往 ZeroJudge 原題

題目描述

題目描述了球從一個完整的二元樹中掉落的過程。球從根節點開始，根據節點的布林值決定往左或往右走。每次球經過一個節點，節點的布林值會翻轉。題目要求計算第 I 個球最終落在哪個葉子節點。

解題思路

這題的解題思路是模擬球掉落的過程。由於二元樹是完整的，我們可以利用二進位來表示節點的編號。每次球掉落時，根據當前節點的布林值，決定往左或往右走。如果往左走，則節點編號不變；如果往右走，則節點編號加一。由於節點的布林值會翻轉，我們可以通過位運算來模擬這個翻轉過程。

具體來說，我們可以將球的編號 I 轉換為二進位形式。然後，從最高位開始，依次判斷每一位是否為 1。如果為 1，則表示球往右走，節點編號加一；如果為 0，則表示球往左走，節點編號不變。每次移動後，將節點編號右移一位，直到到達葉子節點。

然而，題目中提供的程式碼並未直接使用二進位表示和位運算，而是通過迭代模擬了球的掉落過程。程式碼的核心邏輯是根據球的編號 num 的奇偶性來決定球的移動方向。如果 num 是奇數，則球往左走，num 變成 (num + 1) / 2，k 乘以 2；如果 num 是偶數，則球往右走，num 變成 num / 2，k 變成 (k * 2) + 1。這個過程重複 depth - 1 次，最終 k 就是球落到的葉子節點的編號。

複雜度分析

• 時間複雜度: O(depth)。程式碼中包含一個從 0 到 depth - 1 的迴圈，因此時間複雜度與樹的深度成線性關係。
• 空間複雜度: O(1)。程式碼只使用了幾個變數來存儲中間結果，因此空間複雜度是常數級別。

程式碼

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