UVa-679

直接模拟会超时

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxx=21;
 6 int d,n;
 7 bool f[1<<maxx];
 8 int main()
 9 {
10     int T;
11     scanf("%d",&T);
12     while(T--)
13     {
14         memset(f,0,sizeof(f));
15         scanf("%d%d",&d,&n);
16         for(int i=1;i<=n;i++)
17         {
18             int p=1;
19             for(int j=1;j<d;j++)
20             {
21                 if(f[p]==0)
22                 {
23                     f[p]=1;
24                     p=p*2;
25                 }
26                 else
27                 {
28                     f[p]=0;
29                     p=p*2+1;
30                 }
31             }
32             if(i==n) printf("%d
",p);
33         }
34     }
35     scanf("%d",&T);
36 }

可以直接看最后一个小球，看奇偶性。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int d,n;
 6 int main()
 7 {
 8     int T;
 9     scanf("%d",&T);
10     while(T--)
11     {
12         scanf("%d%d",&d,&n);
13         int p=1;
14         for(int i=1;i<d;i++)
15         {
16             if(n%2==1) p=p*2;
17             else p=p*2+1;
18             n=(n+1)/2;
19         }
20         printf("%d
",p);
21     }
22     scanf("%d",&T);
23 }