一开始用java模拟下所有小球的下落过程，结果超时TAT，后来发现是我用了Arrays.fill初始化导致的。。后改用紫书上找到的规律，模拟最后一个小球的过程:
当l是奇数时，它是往左走的第(I+1)/2个小球，否则是往右走的第I/2个小球。最后还由于没删除前面的代码又超时一发。。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStream; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.Arrays; import java.util.Scanner; public class Main { static int d,l,n; public static void main(String[] args) throws IOException { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); while(in.nextToken() != StreamTokenizer.TT_EOF){ n = (int)in.nval; if(n == -1) break; for(int i = 0; i<n; i++){ in.nextToken(); d = (int)in.nval; in.nextToken(); l = (int)in.nval;; solve(); } } } private static void solve() { int k = 1; for(int i = 0; i<d-1; i++){ if(l%2 == 1){ k = 2*k; l = (l+1)/2; } else { k = 2*k+1; l /= 2; } } /*超时TAT * int m = (1<<d)-1;//此处注意<<的优先级小于-,所以要加上括号！ for(int i = 0; i<l; i++){ k = 1; while(true){ judge[k] = !judge[k]; k=judge[k]?2*k:2*k+1; if(k>m) break; } }*/ System.out.println(k); } }