题解：P10884 [COCI 2017-2018#2] San

· · 题解

小清新双向搜索题，难度比卖瓜稍难吧。

idea

双向搜索

看到 n\le 40，很容易想到把整个序列分成两半进行搜索。

对于左半边搜索，每个点枚举经过和不经过。搜索到最后记录这次搜索的总金币数以及最后一个经过的位置的高度 h_i。

对于右半边搜索，记录的是第一个经过的位置的高度 h_j，其他和左半边搜索一样。

我们把左半边搜索的总金币数记为 g_i，右边记为 g_j。

二维偏序

根据题目要求的限制可以得出：h_i\le h_j，还有 k\le g_i+g_j，可以化为 k-g_i\le g_j，明显变成了一个二维偏序的形式，使用树状数组求解即可。

具体的，把所有搜索得到的结果都存入一个结构体数组中，先对 k-g_i 和 g_j 进行离散化，再按照 h_i 排序。

对于左边搜到的，将 k-g_i 加入树状数组，否则答案加上树状数组中所有小于等于 g_j 的数的数量即可。

code

const int nn=41,mm=(1<<20)+5,kk=1e9,hyf=1<<21;//膜拜hhhyyyfff大佬
int n,h[nn],cnt;
ll g[nn],k,ans;
int tree[mm<<1];
inline void add(int x){//树状数组
    for(int i=x;i<=hyf;i+=i&(-i)) tree[i]++;
}
inline int query(int x){
    int tot=0;
    for(int i=x;i>=1;i-=i&(-i)) tot+=tree[i];
    return tot;
}
struct node{
    int h,tp;
    ll g;
};
node x[mm<<1];
inline bool cmp(node l1,node l2){
    return l1.g<l2.g;
}
inline bool cmp2(node l1,node l2){
    if(l1.h==l2.h) return l1.tp<l2.tp;
    return l1.h<l2.h;
}
inline void dfs(int wz,ll sum,int lst){
    if(wz>n/2){
        cnt++;
        x[cnt].h=lst,x[cnt].g=k-sum>0?k-sum:0;
        return ;
    }
    if(lst<=h[wz]) dfs(wz+1,sum+g[wz],h[wz]);
    dfs(wz+1,sum,lst);
}//搜索左边
inline void dfs2(int wz,ll sum,int lst){
    if(wz<=n/2){
        cnt++;
        x[cnt].h=lst,x[cnt].g=sum,x[cnt].tp=1;
        return ;
    }
    if(lst>=h[wz]) dfs2(wz-1,sum+g[wz],h[wz]);
    dfs2(wz-1,sum,lst);
}//搜索右边
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>h[i]>>g[i];
    dfs(1,0,0);
    dfs2(n,0,kk);
    sort(x+1,x+cnt+1,cmp);
    int mzhxi=0;
    ll prvg=-1,bfg;
    for(int i=1;i<=cnt;i++){
        bfg=x[i].g;
        if(x[i].g==prvg) x[i].g=mzhxi;
        else x[i].g=++mzhxi;
        prvg=bfg;//离散化
    }
    sort(x+1,x+cnt+1,cmp2);
    for(int i=1;i<=cnt;i++){
        if(x[i].tp){
            ll sum=query(x[i].g);
            ans+=sum;
        }
        else add(x[i].g);
    }
    cout<<ans<<endl;
    return 0;
}

时间复杂度 O(2^{\frac n 2}\log2^{\frac n 2})。