洛谷 P4799 [CEOI2015 Day2]世界冰球锦标赛

题目相关

题目链接：洛谷 P4799 [CEOI2015 Day2]世界冰球锦标赛

题目描述：

  译自 CEOI2015 Day2 T1「Ice Hockey World Championship」
  今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。
  给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

输入输出格式：

输入格式：
  第一行，两个正整数 $N$ 和 $M(1 \leq N \leq 40,1 \leq M \leq 10^{18})$ ，表示比赛的个数和 Bobek 那家徒四壁的财产。
  第二行，$N$ 个以空格分隔的正整数，均不超过 $10^{16}$，代表每场比赛门票的价格。
输出格式：
  输出一行，表示方案的个数。由于 $N$ 十分大，注意：答案 $\le 2^{40}$。

输入输出样例：

输入#1:
5 1000
100 1500 500 500 1000
输出#1：
8

样例解释：

  八种方案分别是：

• 一场都不看，溜了溜了
• 价格 $100$ 的比赛
• 第一场价格 $500$ 的比赛
• 第二场价格 $500$ 的比赛
• 价格 $100$ 的比赛和第一场价格 $500$ 的比赛
• 价格 $100$ 的比赛和第二场价格 $500$ 的比赛
• 两场价格 $500$ 的比赛
• 价格 $1000$ 的比赛

  说明：

    有十组数据，每通过一组数据你可以获得 $10$ 分。各组数据的数据范围如下表所示：

数据组号	$1-2$	$3-4$	$5-7$	$8-10$
N≤	$10$	$20$	$40$	$40$
M≤	${10}^6$	${10}^{18}$	${10}^6$	${10}^{18}$

博主乱搞

蒟蒻解析：

  1-2组数据，怎么乱搞爆搜都可以。
  3-4组数据，继续暴力出奇迹就可以了。
  5-6组数据，来一个简单的背包即可。
  7-8组数据，emmmmmmmm。。。。。。
  如果直接来 $2^n$ 的搜索就太过暴力。我们需要优雅地处理一下。进入正题：折半搜索（似乎也叫meet in the middle）。
  我们可以把数据分成两块处理，处理完后进行合并，得到答案，把复杂度降下来。这就是折半搜索的原理，一般需要两组数据能进行所谓的合并统计。为了尽量降低复杂度，我们一般对数据进行均分。
  对于本题，我们也可以把数据从中间分成两部分。对于前后两部分，我们分别求出每种买票情况以及每个情况对应的花费。
  然后我们对其中的一部分 $A$ 进行枚举，判断另一部分 $B$ 中有多少能与 $A$ 合并后符合要求。所以我们对 $B$ 中元素排序，每一次二分搜索最大能接受的数即可。对于其之前的都是符合要求的。
  具体代码如下：

蒟蒻代码：

cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
#define ll long long 
#define il inline
il ll read(){
    ll x=0; int f=1; char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1; ch=getchar(); 
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();
    }
    return x*f;
}
const int maxn=45;
ll ans,m,p[maxn];
int n,lst,mid;
ll sa[1050000],sb[1050000];
void dfs(ll *a,ll sum,int now){
    if (sum>m) return;
    if (now>lst){
        a[++a[0]]=sum; return;
    }
    dfs(a,sum+p[now],now+1);
    dfs(a,sum,now+1);
}
il ll getsum(ll rem){
    int l=1,r=sa[0]; ll tmp=0;
    while (l<=r){
        int mid=(l+r)>>1;
        if (sa[mid]>rem){
            r=mid-1;
        }else{
            tmp=mid; l=mid+1;
        }
    }
    return tmp;
} 
int main(){
    n=read(); m=read(); 
    for (int i=1;i<=n;++i) p[i]=read();
    lst=(n+1)>>1; dfs(sa,0,1);
    lst=n; dfs(sb,0,((n+1)>>1)+1);
    sort(sa+1,sa+1+sa[0]);
    for (int i=1;i<=sb[0];++i){
        ans+=getsum(m-sb[i]);
    }
    printf("%lld",ans);
    return 0;
}