2021“MINIEYE杯”中国大学生算法设计超级联赛（3）题解

题目目录：1011 1007 1004
1011题 Segment Tree with Pruning（带修建的分段树）
题目大意：给出n和k，要求在区间【1，n】上建左右子树，当左右子树的区间长度小于k时则停止建树（剪枝），输出总的结点个数。

思路：由于建树的最终结点个数只和区间长度有关，而与左右端点无关，用左右分支的区间长度来求其中的结点个数再加上根结点，并且用map保存出现过的区间长度对应的结点个数，这样会大大降低时间复杂度。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k; 
map<ll,ll> mp;//由ll类型映射到ll类型，通过下标访问
ll build(ll r){//区间长度一样的情况下，其实画出的树也是一样的 
    if(mp.find(r)!=mp.end()) return mp[r];
    if(r<=k) return mp[r]=1;
    return mp[r]=build(r/2)+build(r-r/2)+1;//自己加上左右树的结点个数 
}
int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        mp.clear();
        cout<<build(n)<<endl;
    }
    return 0;
} 

1007题 Photoshop Layers（Photoshop图层）
题目大意：
思路：