UVa679
通过模拟每个小球的下落过程会TLE，下面是TLE代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
using namespace std;
int s[1<<MAXN];
int main()
{
int d, I,n;
cin >> n;
while (n--) {
cin >> d;
if (d == -1)break;
cin >> I;
memset(s, 0, sizeof(s));
int k;
for (int i = 0; i < I; i++)
{
k = 1;
for (;;)
{
int flag = s[k];
s[k] = !s[k];
if (flag)k = k * 2 + 1;
else k = k * 2;;
if (k > ((1 << d) - 1))break;
}
}
cout << k / 2 << endl;
}
return 0;
}
但其实每个小球在根节点处，如果上一个小球向左，那这个小球就向左，因此对于一个根节点来说，该球是第奇数个小球到达该节点的，则一定向左，若是第偶数个小球，则向右。直接模拟第I个小球的下落轨迹，并每下落一层，I=I/2或者I=(I+1)/2,因为有一半的小球落向了另一个方向，该小球对下一个节点来说就是第
I=I/2或者I=(I+1)/2个，1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int main()
{
int d, I,n;
cin >> n;
while (n--) {
cin >> d;
if (d == -1)break;
cin >> I;
int k = 1;
for (int i = 0; i < d-1; i++)
{
if (I % 2) { k = k * 2 ; I = (I + 1) / 2; }//向左走
else { k = k * 2+1; I = I / 2; }//向右走
}
cout << k << endl;
}
return 0;
}