【题目来源】
洛谷：[P4799 CEOI 2015] 世界冰球锦标赛 (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}\)。
【输入样例】
5 1000
100 1500 500 500 1000
【输出样例】
8
【算法标签】
《洛谷 P4799 世界冰球锦标赛》 #搜索# #折半搜索meet in the middle# #CEOI（中欧）# #2015#
【代码详解】
// 40分版本
#include <bits/stdc++.h>
using namespace std;#define int long long // 将int定义为long long类型，避免大数溢出const int N = 45; // 数组最大容量
int a[N], n, m, cur, ans = 1; // a: 存储有效数字，n: 输入数字总数，m: 目标值，cur: 有效数字计数，ans: 方案数（初始为1表示空集）// 深度优先搜索，计算所有子集和不超过m的方案数
void dfs(int step, int x)
{// 剪枝：如果剩余可用数字的最小值已经超过当前剩余容量xif (x < a[step]){return;}// 从step位置开始遍历所有可能的数字for (int i = step; i <= cur; i++){// 如果当前数字可以加入子集if (x >= a[i]){ans++; // 增加方案数（选择当前数字）dfs(i + 1, x - a[i]); // 递归搜索下一个数字}else {return; // 由于数组已排序，后续数字更大，直接返回}}
}signed main() // 使用signed main()替代int main()，因为int被重定义为long long
{cin >> n >> m; // 读入数字总数n和目标值m// 筛选有效数字（不大于m的数字）for (int i = 1; i <= n; i++){int x;cin >> x;if (x > m) continue; // 跳过大于m的数字a[++cur] = x; // 存储有效数字}// 对有效数字进行升序排序，便于剪枝sort(a + 1, a + cur + 1);// 开始深度优先搜索dfs(1, m);// 输出所有子集和不超过m的方案数cout << ans;return 0;
}
// 满分版本
#include <bits/stdc++.h>
using namespace std;#define int long long // 将int定义为long long类型，避免大数溢出const int N = 45; // 数组最大容量
int a[N], n, m, cur, ans = 1; // a: 存储有效数字，n: 输入数字总数，m: 目标值，cur: 有效数字计数，ans: 方案数（初始为1表示空集）
vector<int> sa, sb; // sa: 前半部分数字的子集和，sb: 后半部分数字的子集和// 深度优先搜索，生成子集和
void dfs(int pos, int x, int type)
{// 剪枝：如果剩余可用数字的最小值已经超过当前剩余容量if (m - x < a[pos]){return;}// 确定搜索范围int end = cur; // 默认搜索到末尾if (type == 0) // 如果是搜索前半部分{end = cur / 2; // 只搜索到中间位置}// 从pos位置开始遍历数字for (int i = pos; i <= end; i++){// 如果当前数字可以加入子集if (m - x >= a[i]){// 将新子集和存入对应向量if (type == 0){sa.push_back(x + a[i]);}else{sb.push_back(x + a[i]);}// 递归搜索下一个数字dfs(i + 1, x + a[i], type);}else{return; // 由于数组已排序，后续数字更大，直接返回}}
}signed main() // 使用signed main()替代int main()，因为int被重定义为long long
{cin >> n >> m; // 读入数字总数n和目标值m// 筛选有效数字（不大于m的数字）for (int i = 1; i <= n; i++){int x;cin >> x;if (x > m) continue; // 跳过大于m的数字a[++cur] = x; // 存储有效数字}// 对有效数字进行升序排序，便于剪枝sort(a + 1, a + cur + 1);// 分治：将数字分成前后两部分，分别生成子集和dfs(1, 0, 0); // 搜索前半部分数字dfs(cur / 2 + 1, 0, 1); // 搜索后半部分数字// 对子集和数组进行排序，便于使用二分查找sort(sa.begin(), sa.end());sort(sb.begin(), sb.end());// 合并两部分结果：计算sa[i] + sb[j] <= m的方案数for (int i = 0; i < sb.size(); i++){// 对于sb中的每个和，找到sa中满足sa[j] <= m - sb[i]的最大索引int x = m - sb[i];int pos = upper_bound(sa.begin(), sa.end(), x) - sa.begin();ans += pos; // 增加满足条件的方案数}// 加上单一部分的方案数（只使用前半部分或后半部分数字）ans += sa.size(); // 只使用前半部分数字的方案ans += sb.size(); // 只使用后半部分数字的方案// 输出所有子集和不超过m的方案数cout << ans;return 0;
}
【运行结果】
5 1000
100 1500 500 500 1000
8