【CEOI2015 Day2】世界冰球锦标赛（ 提高+/省选-） 题解

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

第一行，两个正整数 N N N 和 M ( 1 ≤ N ≤ 40 , 1 ≤ M ≤ 1 0 18 ) M(1 leq N leq 40,1 leq M leq 10^{18}) M(1≤N≤40,1≤M≤1018)，表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行， N N N 个以空格分隔的正整数，均不超过 1 0 16 10^{16} 1016，代表每场比赛门票的价格。

输出一行，表示方案的个数。由于 N N N 十分大，注意：答案 ≤ 2 40 le 2^{40} ≤240。

5 1000
100 1500 500 500 1000

8

八种方案分别是：

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

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

分析：
40pts做法就是纯爆搜。具体看代码注释

#include
using namespace std;
long long n;
long long ans=0;
long long m;
long long a[10000000];
void dfs(long long dep,long long sum){  //层数，当前层的总和值
	if(sum>m){   //边界，如果总和大于手上现有的钱，肯定得回溯。
		return;
	}
	if(dep==n+1){ //还是边界，如果层数到了最底的一层，那就证明找到了一组可行解的情况
		ans++;
		return ;
	}	
	dfs(dep+1,a[dep]+sum);//更新sum
	dfs(dep+1,sum);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	} 
	dfs(1,0);
	cout< 
70pts做法就是带上一个背包，我们发现买票的状态类似于背包，写上一个分段：
 
#include
using namespace std;
long long ans;
long long n,m;
long long a[10000000];
long long f[10000000];
inline void dfs(long long dep,long long sum){
   if(sum>m)return;
   if(dep==n+1){
       ans++;
       return;
   }
   dfs(dep+1,sum+a[dep]);
   dfs(dep+1,sum);
}
int main(){
   cin>>n>>m;
   for(int i=1;i<=n;i++)cin>>a[i];
   if(n<=20){
       dfs(1,0);
       printf("%lldn",ans);
   }
   else if(n<=40&&m<=1e6){
   		f[0]=1;
   		for(int i=1;i<=n;i++){
   			for(int j=m;j>=a[i];j--){
   				f[j]=f[j]+f[j-a[i]];	
			}
		}
		for(int i=0;i<=m;i++){
			ans=ans+f[i];
		}
		printf("%lldn",ans);
   }
   return 0;
}
 
100pts做法：
 这里介绍一个折半搜索的思路。
 因为
    
     
      
       
        N
       
       
        ≤
       
       
        40
       
       
        ,
       
       
        O
       
       
        (
       
       
        
         2
        
        
         40
        
       
       
        )
       
      
      
       Nleq40 ,O(2^{40})
      
     
    N≤40,O(240)的爆搜一定会
    
     
      
       
        T
       
       
        L
       
       
        E
       
      
      
       TLE
      
     
    TLE，所以我们将
    
     
      
       
        N
       
      
      
       N
      
     
    N分成两份
 
搜索
    
     
      
       
        1
       
      
      
       1
      
     
    1到
    
     
      
       
        n
       
       
        /
       
       
        2
       
      
      
       n/2
      
     
    n/2和
    
     
      
       
        n
       
       
        /
       
       
        2
       
       
        +
       
       
        1
       
      
      
       n/2+1
      
     
    n/2+1到
    
     
      
       
        n
       
      
      
       n
      
     
    n，让复杂度降到
    
     
      
       
        O
       
       
        (
       
       
        
         2
        
        
         
          n
         
         
          /
         
         
          2
         
         
          +
         
         
          1
         
        
       
      
      
       O(2^{n/2+1}
      
     
    O(2n/2+1+组合答案的复杂度
    
     
      
       
        )
       
       
        )
       
      
      
       ))
      
     
    ))。
 
将前一半的搜索状态存入
    
     
      
       
        a
       
      
      
       a
      
     
    a数组，后一半存入
    
     
      
       
        b
       
      
      
       b
      
     
    b数组。
 
mid=n>>1;
dfs(1,mid,0,suma,cnta);
dfs(mid+1,n,0,sumb,cntb);
 
难点主要在于最后答案的组合统计。
 
我们可以现将
    
     
      
       
        a
       
      
      
       a
      
     
    a或
    
     
      
       
        b
       
      
      
       b
      
     
    b数组
    
     
      
       
        s
       
       
        o
       
       
        r
       
       
        t
       
      
      
       sort
      
     
    sort。然后通过枚举另一个数组中的状态，来实现统计答案。
 
(借用洛谷上面的一张图）
 
 
	sort(suma+1,suma+1+cnta);
	for(int i=1;i<=cntb;i++){
		ans=ans+upper_bound(suma+1,suma+1+cnta,m-sumb[i])-suma-1;
	}
 
则我们就可以写出满分程序了
 
#include
using namespace std;
long long n,m;
long long a[10000000];
long long w[10000000];
long long suma[10000000];
long long sumb[10000000];
long long cnta,cntb,ans;
void dfs(long long Left,long long Right,long long sum,long long a[],long long &cnt){
	if(sum>m) return ;
	if(Left>Right){
		a[++cnt]=sum;
		return ;
	}
	dfs(Left+1,Right,sum+w[Left],a,cnt);
	dfs(Left+1,Right,sum     ,a,cnt);
}
int main(){
	
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&w[i]);
	}
	long long mid=n>>1;
	dfs(1,mid,0,suma,cnta);
	dfs(mid+1,n,0,sumb,cntb);
	sort(suma+1,suma+1+cnta);
	for(int i=1;i<=cntb;i++){
		ans=ans+upper_bound(suma+1,suma+1+cnta,m-sumb[i])-suma-1;
	}
	printf("%lld",ans);
	return 0;
}