[CEOI2015 Day2]世界冰球锦标赛（双向搜索）

2023-08-05 17:07:16

题目描述

[CEOI2015 Day2]世界冰球锦标赛译自 CEOI2015 Day2 T1「Ice Hockey World Championship」

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入格式：

第一行，两个正整数 N 和 $ M(1 \leq N \leq 40,1 \leq M \leq 10^{{18})M(1≤N≤40,1≤M≤10}{18}) $ ，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行，N 个以空格分隔的正整数，均不超过 $ 10^{16}1016 $ ，代表每场比赛门票的价格。

输出格式：

输出一行，表示方案的个数。由于 NN 十分大，注意：答案 $ \le 2^{40}≤2{40} $ 。

输入样例：

5 1000

100 1500 500 500 1000

输出样例1：

说明

样例解释:八种方案分别是：

一场都不看，溜了溜了

价格 100 的比赛

第一场价格 500 的比赛

第二场价格 500 的比赛

价格 100 的比赛和第一场价格 500 的比赛

价格 100 的比赛和第二场价格 500 的比赛

两场价格 500 的比赛

价格 1000 的比赛

solution:

非常经典的双向搜索，先枚举前20场比赛看不看，将所有方案会花的钱的数目存入数组中，再枚举后20场比赛看不看，将结果存入第二个数组中。将第二个数组排个序，遍历第一个数组，二分找到每一个元素在二号数组中能匹配的最大下标，然后直接加到ans中去即可。

=>

code:

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

int n,midd;

ll a[41],m,ans,t1,t2;

ll l[1200001];

ll r[1200001];

inline ll qr(){

    char ch;

    while((ch=getchar())<'0'||ch>'9');

    ll res=ch^48;

    while((ch=getchar())>='0'&&ch<='9')

        res=res*10+(ch^48);

    return res;

}

inline void dfs1(int t,ll tot){

    if(t==midd){

        l[++t1]=tot;

        return ;

    }dfs1(t+1,tot);

    if(tot+a[t]<=m)

        dfs1(t+1,tot+a[t]);

}

inline void dfs2(int t,ll tot){

    if(t>n){

        r[++t2]=tot;

        return ;

    }dfs2(t+1,tot);

    if(tot+a[t]<=m)

        dfs2(t+1,tot+a[t]);

}

inline int get(ll t){

    int x=1,y=t2,mid;

    while(x<=y){

        mid=(x+y)>>1;

        if(t<r[mid])y=mid-1;

        else x=mid+1;

    }return y;

}

int main(){

    //freopen(".in","r",stdin);

    //freopen(".out","w",stdout);

    n=qr(),m=qr();midd=n/2+1;

    for(rg i=1;i<=n;++i)

        a[i]=qr();

    dfs1(1,0); dfs2(midd,0);

    sort(r+1,r+t2+1);

    for(rg i=1;i<=t1;++i)

        ans+=get(m-l[i]);

    printf("%lld\n",ans);

    return 0;

}

码农公寓