[CEOI2015 Day2]世界冰球锦标赛

我要成为李学传人！！！

传送门

莫名其妙的开始更博了 ，随便水两句吧。

从一个神仙的OI总结里看到了这题，学习了一波折半搜索的姿势向blog添加了一道搜索标签的题。

暴力搜索$2^{40}$，除非加李学剪枝巨斧砍大树根本不可能，不过随便加个剪枝就有87分。

而所谓折半搜索就是把搜索分成两半然后拼起来，对于某些没有多项式时间复杂度解的题目（指loli的搜索题）有不错的效果。

只要把前20个和后20个的所有方案及其花费都存下来，枚举在前面20个的花费，在后面二分看看能匹配多少个就好了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll p[50],a[50],sum[50],m,ans;
ll o[2][1050001],num[2];
int n,mid;
void dfs(int x,ll y,int z){
    if ((z==0&&x==mid+1)||(z==1&&x==n+1)){
        o[z][++num[z]]=y;
        return;
    }
    if (a[x]+y<=m) dfs(x+1,y+a[x],z);
    dfs(x+1,y,z);
}
inline int find(ll x){
    int l=1,r=num[1],mid,res=0;
    while (l<=r){
        mid=(l+r)>>1;
        if (o[1][mid]<=x) res=mid,l=mid+1;
        else r=mid-1;
    }
    return res;
}
int main(){
    scanf("%d%lld",&n,&m);
    for (int i=1; i<=n; i++) scanf("%lld",&a[i]);
    sort(a+1,a+n+1); p[0]=1;
    for (int i=1; i<=n; i++)
        sum[i]=a[i]+sum[i-1],p[i]=(p[i-1]<<1);
    mid=n>>1;
    dfs(1,0,0); dfs(mid+1,0,1);
    sort(o[1]+1,o[1]+num[1]+1);
    for (int i=1; i<=num[0]; i++)
        ans+=find(m-o[0][i]);
    printf("%lld\n",ans);
    return 0;
}