＊＊＊1070. 下落的小球

题目：


代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 11111111
using namespace std;
int n;
bool a[maxn];
int power(int x)
{
    int res=1;for(int i=1;i<=x;i++){
    res<<=1;}return res;
}
int main()
{
    cin>>n;int D,I;for(int i=1;i<=n;i++){
    cin>>D>>I;memset(a,0,sizeof(a));for(int j=1;j<=I;j++){
    int temp=1;//cout<<"D="<<power(D)<<endl;while(temp<power(D)){
    //cout<<"j="<<j<<" "<<temp<<endl;a[temp]^=1; //cout<<"temp="<<temp<<" "<<"a[temp]="<<a[temp]<<endl;if(j==I&&temp*2>=power(D)) {
    cout<<temp<<endl;break;}if(a[temp]) temp*=2;else temp=temp*2+1;}}}return 0;
}

优化过的版本：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 1048888
using namespace std;
int n;
bool a[maxn];
int main()
{
    cin>>n;int D,I;for(int i=1;i<=n;i++){
    cin>>D>>I;int x=1<<D;memset(a,0,x);int temp;for(int j=1;j<=I;j++){
    temp=1;while(temp<x){
    a[temp]^=1;if(a[temp]) temp<<=1;else temp=temp<<1|1;}}cout<<(temp>>1)<<endl;}return 0;
}