记录
23:28 2023-4-16
https://onlinejudge.org/external/6/679.pdf
reference:《算法竞赛入门经典第二版》例题6-6
二叉树,这里是完全二叉树,使用模拟的方式应该会TLE(虽然我用模拟的方式也TLE了,但不是这个原因,下面会提到原因)
不用模拟的方式,转换思路,使用递归的方式去思考。
这里是完全二叉树,使用数组模拟完全二叉树。
对于每个小球,肯定会经过根节点(先考虑D=1的时候的根节点)(在数组完全二叉树中位置为1),对于这个根节点来说,标号为奇数的小球肯定走左子树,为偶数的小球肯定走右子树。
对于走左子树的小球,此时把左边这个做为新的根节点(D=2,在数组完全二叉树中位置为2),继续对进入左边的小球进行判断,奇数继续走左子树,偶数继续走右子树。
小球编号 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
数组下标为1作为根 | 1(走1的左子树) | 1(走1的右子树) | 2(走1的左子树) | 2(走1的右子树) |
数组下标为2作为根 | 1(走2的左子树) | 2(走2的右子树) |
我TLE的原因是,书上和Uva网站上的题不是相同的。。输入就是有问题的。。还是要看原来的题的表述
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#define MAX_N 20
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;
int arr[1 << MAX_N];
int N, D, I;
void solve() {
fill(arr, arr + (1 << MAX_N), 0);
int k = 1, n = (1 << D) - 1;
for(int i = 0; i < I; i++) {
k = 1;
for(;;) {
arr[k] = !arr[k];
k = arr[k]? 2 * k : 2 * k + 1;
if(k > n) break;
}
}
printf("%d\n", k / 2);
}
void solve1() {
int k = 1;
for(int i = 0; i < D-1; i++) {
if(I % 2 == 1) {
k = k * 2;
I = (I + 1) / 2;
} else {
k = k * 2 + 1;
I = I / 2;
}
}
printf("%d\n", k);
}
//solve 会TLE
int main() {
scanf("%d\n", &N);
for(int i = 0; i < N; i++){
scanf("%d%d", &D, &I);
solve1();
}
// while (scanf("%d%d", &D, &I) == 2) {
// solve1();
// }
}
标签:左子,Balls,679,int,小球,二叉树,TLE,include
From: https://www.cnblogs.com/57one/p/17324483.html