线段树什么的最讨厌了

发表于 |
字数统计: 318 | 阅读时长 ≈ 1
  • Code Level: ※
  • Thinking Level: ※

Description

给出最小的n使得区间[l,r]出现在了build(1,0,n)建出的线段树中，若无解（在limit范围内）输出-1

1
2
3
4
5
void build(int now,int l,int r){
    if(l==r) return ;
    int mid=l+r>>1;
    build(now*2,l,mid); build(now*2+1,mid,r);
}

Solution

每一个点寻找它的父亲，共四种选择，都搜索一下即可
重点是此类搜索的剪枝，应考虑它的存在特性
比如在此题，因为线段树是二叉树，所以可以用它作为一个子树其是否具有左侧森林（同层而言）来剪枝

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int t,ll,rr,lim,ans;
void search(int l,int r){
    if(l<0||l>r) return ; if(ans!=-1&&ans<=r) return ; if(r>lim) return ;
    if(l==0){ if(ans==-1||ans>r) ans=r; return ; }
    int len=r-l+1;
    search(l-len,r);
    if(l-len-1>=2*len-1||l-len-1==0) search(l-len-1,r);
    if(l>=2*len) search(l,r+len);
    if(l>=2*len-1) search(l,r+len-1);
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&ll,&rr,&lim); ans=-1; search(ll,rr);
        printf("%d\n",ans);
    }
    return 0;
}

总结

搜索剪枝考虑一定要周全
思考搜索本身的性质