题解 P4799 【[CEOI2015 Day2]世界冰球锦标赛】

双向搜索好题

传送门

实际上，双向搜索就是把\(a^n\)的复杂度转变成了大多为\(O(nlogna^{\frac{n}{2}})\)的复杂度。

上代码

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<bitset>

#include<vector>

#include<map>

#include<ctime>

#include<cstdlib>

#include<set>

#include<bitset>

#include<stack>

#include<list>

#include<cmath>

using namespace std;

#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)

#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)

#define ERP(t,a) for(int t=head[a];t;t=e[t].nx)

#define Max(a,b) ((a)<(b)?(b):(a))

#define Min(a,b) ((a)<(b)?(a):(b))

#define TMP template<class ccf>

#define lef L,R,l,mid,pos<<1

#define rgt L,R,mid+1,r,pos<<1|1

#define midd register int mid=(l+r)>>1

#define chek if(R<l||r<L)return

#define all 1,n,1

#define pushup(x) seg[(x)]=seg[(x)<<1]+seg[(x)<<1|1]

typedef long long ll;

TMP inline ccf qr(ccf k){

    char c=getchar();

    ccf x=0;

    int q=1;

    while(c<48||c>57)

	q=c==45?-1:q,c=getchar();

    while(c>=48&&c<=57)

	x=x*10+c-48,c=getchar();

    if(q==-1)

	x=-x;

    return x;

}

const int maxn=2097155;

ll data[45];

ll ord[maxn];

ll ans;

ll n;

ll m;int cnt;

inline ll C(ll k){

    ll mid,l=1,r=cnt;

    do{

	mid=(l+r)>>1;

	if(ord[mid]<=k)

	    l=mid+1;

	else

	    r=mid-1;

    }while(l<=r);

    return l;

}

void dfs(int now,ll rest){

    if(now>(n>>1))return void(ord[++cnt]=m-rest);

    if(rest>=data[now])

	dfs(now+1,rest-data[now]);

    dfs(now+1,rest);

}

void dfs2(int now,ll rest){

    if(now>n) return void(ans+=C(rest)-1ll);

    if(rest>=data[now])

	dfs2(now+1,rest-data[now]);

    dfs2(now+1,rest);

}

int main(){

#ifndef ONLINE_JUDGE

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

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

#endif

    n=qr(1ll);

    m=qr(1ll);

    RP(t,1,n)

	data[t]=qr(1ll);

    dfs(1,m);

    sort(ord+1,ord+cnt+1);

    dfs2(n/2+1,m);

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

    return 0;

}