《P4799 [CEOI 2015] 世界冰球锦标赛 (Day2)》
题目描述
译自 CEOI2015 Day2 T1「Ice Hockey World Championship」
今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。
给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。
输入格式
第一行，两个正整数 N 和 M(1≤N≤40,1≤M≤1018)，表示比赛的个数和 Bobek 那家徒四壁的财产。
第二行，N 个以空格分隔的正整数，均不超过 1016，代表每场比赛门票的价格。
输出格式
输出一行，表示方案的个数。由于 N 十分大，注意：答案 ≤240。
输入输出样例
输入 #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≤ | 10 | 20 | 40 | 40 |
| M≤ | 106 | 1018 | 106 | 1018 |
代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
// 生成所有可能的子集和
vector<ll> generateSubsetSums(const vector<ll>& prices) {
vector<ll> sums;
int n = prices.size();
// 枚举所有子集，使用位运算
for (int mask = 0; mask < (1 << n); mask++) {
ll sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
sum += prices[i];
}
}
sums.push_back(sum);
}
return sums;
}
int main() {
int N;
ll M;
cin >> N >> M;
vector<ll> prices(N);
for (int i = 0; i < N; i++) {
cin >> prices[i];
}
// 将数组分成两半
int mid = N / 2;
vector<ll> left(prices.begin(), prices.begin() + mid);
vector<ll> right(prices.begin() + mid, prices.end());
// 生成左右两部分的所有子集和
vector<ll> leftSums = generateSubsetSums(left);
vector<ll> rightSums = generateSubsetSums(right);
// 对右半部分的子集和进行排序，以便二分查找
sort(rightSums.begin(), rightSums.end());
ll ans = 0;
// 使用传统for循环替代基于范围的for循环
for (int i = 0; i < leftSums.size(); i++) {
ll s = leftSums[i];
if (s > M) continue; // 超过预算，跳过
ll target = M - s;
// 显式指定迭代器类型，替代auto
vector<ll>::const_iterator it = upper_bound(rightSums.begin(), rightSums.end(), target);
// 直接计算偏移量，替代distance函数
ans += (it - rightSums.begin());
}
cout << ans << endl;
return 0;
}