###Pro：2015上海区域赛B题
题意：一颗编号为 1 2 3 2^k 2^k+1…的满二叉树，从root点初始num=0，开始向下遍历k层，加 或 减去编号，使得num等于N；
题解：注意题目条件，N <= 2^k <= 2^60,所以一个N，是可以被最左边一条边（1,4,8，，2 ^ k)表示,或者被次左（1,2,4，，2 ^ k + 1)表示;
若设x为+的数，那么
x-（2^k-x)=n;
x=(2^k+n)/2
=_=大概是这个理，分奇数，偶数讨论下
代码:
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
32
33
34
35
36
37
38
39
40
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
int T, cas=0;
scanf("%d",&T);
while(T--){
int n,k;
scanf("%d%d",&n,&k);
printf("Case #%d:\n",++cas);
LL x;
if(n&1){
x=((1L<<k)-1+n)>>1;
for(int i=0;i<k;i++){
if(x&1) printf("%lld +\n",1L<<i);
else printf("%lld -\n",1L<<i);
x>>=1;
}
}
else{
x=(((1L<<k)+n)>>1)-1;
for(int i=0;i<k;i++){
if(i==k-1){
if(x&1) printf("%lld +\n",1L<<i|1);
else printf("%lld -\n",1L<<i|1);
}
else{
if(x&1) printf("%lld +\n",1L<<i);
else printf("%lld -\n",1L<<i);
}
x>>=1;
}
}
}
return 0;
}
|
END