[CEOI2015 Day2]世界冰球锦标赛 (双向搜索)

题目描述

[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:

8

说明

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

一场都不看,溜了溜了

价格 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;
}
上一篇:python3 正则匹配[^abc]和(?!abc)的区别(把多个字符作为一个整体匹配排除)


下一篇:备忘-vs2015实用插件