本文主要是介绍UVa679 小球下落（树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=620
给下落的深度和小球个数，小球依次下落，结点有个开关，每到一个结点，开关关向左，开向右
一开始想到了简单模拟，结果超时…
#include <cstdio>
#include <iostream>
#include <cstring>
#define maxn 20
using namespace std;int s[1<<maxn];int main(){int n,D,I,now=1;scanf("%d",&n);while(n--){scanf("%d%d",&D,&I);int last=(1<<D)-1;//最后结点，临界 // cout<<"last="<<last<<endl;memset(s,0,sizeof(s));while(I--){now=1;while(1){ if(s[now]==0){int temp= 2*now;s[now]=1;now=temp;}else{int temp= 2*now+1;s[now]=0;now=temp; }if(now>last) break; }} printf("%d\n",now/2);}return 0;
}
后来开了刘汝佳老师算法入门，发现缺失需要多读题，注意细节，多思考。
I小球个数的奇偶性很有关系。奇数的话也是往左走的(I+1)/2个小球，偶数是往右走的I/2个小球。
#include <cstdio>
#include <iostream>
#include <cstring>
#define maxn 20
using namespace std;int s[1<<maxn];int main(){int n,D,I,now=1;scanf("%d",&n);while(n--){scanf("%d%d",&D,&I);int k=1;for(int i =0;i<D-1;i++){if(I%2!=0){k=2*k;I=(I+1)/2;}else{k=2*k+1;I=I/2;}}printf("%d\n",k);}return 0;
}
这篇关于UVa679 小球下落（树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
