点击查看目录
算法实现
我们正常的搜索应该是一个指数级的：\(2^n\)。
然而我们可以把这个搜索拆成两半，设小于整张图的限制 \(limit\) 为合法：
对于上半搜索，我们有若干符合限制的答案 \(sum_1\)，对于下半搜索，我们有若干符合限制的答案 \(sum_2\)。
因此对于下半搜索，有一个匹配的限制：\(limit-sum_2[i],i\in sum_2\)，在这个限制下，有多个上半搜索的匹配，类似于：
杂题乱写
[CEOI2015 Day2] 世界冰球锦标赛
折叠题干
[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
样例输入 #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 \leq\) | \(10\) | \(20\) | \(40\) | \(40\) |
| \(M \leq\) | \(10^6\) | \(10^{18}\) | \(10^6\) | \(10^{18}\) |
这不板子题（
Miku's Code
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
#define MYMAX 20070831
typedef long double llf;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-8;
int Max(int x,int y)<%if(x<y) return y;return x;%>
int Min(int x,int y)<%if(x<y) return x;return y;%>
int Abs(int x)<%if(x<0) return x*(-1);return x;%>
#if ONLINE_JUDGE
char in[1<<20],*p1=in,*p2=in;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
inline ll read(){
char c=getchar();
ll x=0,f=1;
while(c<48)<%if(c=='-')f=-1;c=getchar();%>
while(c>47)x=(x*10)+(c^48),c=getchar();
return x*f;
}const int maxn=45;
int n;
ll m,cost[maxn];
vector<ll> s1,s2;
void dfs(int st,int to,ll sum,vector<ll>&now){
if(sum>m) return;
if(st>to){
now.push_back(sum);
return;
}
dfs(st+1,to,sum+cost[st],now);
dfs(st+1,to,sum,now);
}
int main(){
n=read(),m=read();
for(rg i=1;i<=n;++i) cost[i]=read();
dfs(1,n/2,0,s1);
dfs(n/2+1,n,0,s2);
sort(s1.begin(),s1.end());
ll ans=0;
int len2=s2.size()-1;
for(rg i=0;i<=len2;++i) ans+=upper_bound(s1.begin(),s1.end(),m-s2[i])-s1.begin();
printf("%lld\n",ans);
}