[luogu4799 CEOI2015 Day2] 世界冰球锦标赛(折半搜索)

Solution

折半搜索裸题,注意\(long long\)

Code

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define Re register

#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)

#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)

using namespace std;

typedef long long LL;

inline LL read() {

	LL x=0,f=1;char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int N=45;

LL n,m,k,t1,t2,ans;

LL da[N],s1[1050000],s2[1050000];

void dfs1(int pos,LL s) {

	if(s>m) return ;

	if(pos==k+1) {s1[++t1]=s;return ;}

	dfs1(pos+1,s); dfs1(pos+1,s+da[pos]);

}

void dfs2(int pos,LL s) {

	if(s>m) return ;

	if(pos==n+1) {s2[++t2]=s;return ;}

	dfs2(pos+1,s); dfs2(pos+1,s+da[pos]);

}

int main() {

	n=read(),m=read();k=n/2;

	Fo(i,1,n) da[i]=read();

	dfs1(1,0);dfs2(k+1,0);

	sort(s1+1,s1+1+t1); sort(s2+1,s2+1+t2);

	LL p1=1,p2=t2;

	while(p1<=t1&&p2) {

		while(p2&&s1[p1]+s2[p2]>m) p2--;

		ans+=p2; p1++;

	}

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

	return 0;

}

巴特西

[luogu4799 CEOI2015 Day2] 世界冰球锦标赛(折半搜索)

Solution

Code

最新文章

热门文章