HDU 5323 Solve this interesting problem(2015多校联合)

发表于   |  

题目链接：

戳我

题目大意

$0….n$ 建立线段树，问是否存在 区间为 L R 的 这个叶子节点，存在找到最小的$n$，不存在输出$-1$

样例解释

6 7 //线段树Build(0, 7)，刚好存在6 7这个叶子节点，故输出7
10 13 // 不存在
10 11 //同理

解题思路

根据线段树 父亲节点的区间 和 孩子节点的 区间的关系，可得知 若孩子节点时l，r，则父亲节点有4种情况(见代码注释),依次枚举即可。
但要注意 剪枝。

代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;

const int inf = 0x3f;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6+5;
int L, R, ans;
void dfs(int l, int r)
{
    if(r < l || r < 0 || l < 0) return;
    if(r > 2*R) return;
    if(ans != -1 && r >= ans) return;
    if(l == 0)
    {
        ans = r;
        return;
    }

    //printf("l = %d, r = %d\n", l, r);
    int x, y;
    // (x+r) / 2 + 1 = l x+r为偶数
    x = (l - 1) * 2 - r;
    dfs(x, r);
    //(x+r-1) / 2 + 1 = l  x+r为奇数
    x = (l - 1) * 2 + 1 - r;
    dfs(x, r);
    //(l + y) / 2 = r
    y = 2 * r - l;
    dfs(l, y);
    //(l + y - 1) / 2 = r
    y = 2 * r + 1 - l;
    dfs(l, y);
}

int main()
{
    while(~scanf("%d %d", &L, &R))
    {
        ans = -1;
        dfs(L, R);
        printf("%d\n", ans);
    }
    return 0;
}