

BZOJ4800 世界冰球锦标赛

题面

题目描述

有 $n$ 个物品，$m$ 块钱，给定每个物品的价格，求买物品的方案数。

输入格式

第一行两个数 $n，m$ 代表物品数量及钱数

第二行 $n$ 个数，代表每个物品的价格

$n\leq 40，m\leq 10^{18}$

输出格式

一行一个数表示购买的方案数

（想怎么买就怎么买，当然不买也算一种）

题解

meet_in_the_middle的模板题，直接暴力就行。

将物品分成左边和右边两半先将左边一半（最多有 $20$ 个数）的所有方案状压起来存进数组中，设 $v[S]$ 为状态为 $S$ 时所有权值和，将数组排序后，枚举右边一半的所有方案，用 $lower\_bound$ 求出对于左边数组有多少个方案满足和当前方案权值总和小于 $m$ 。

有几个优化方法（我也不确定到底有没有实际作用）：

• 使用 $lowbit$ 枚举某一个方案的所有为 $1$ 的位。
• 预处理出 $(1 << 0) - (1 << 20)$ 的 $log$ 是多少。
• 用 $lower\_bound$ 快速求左边对应有多少个方案满足。
• 快读

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define MAX_N 1050007
typedef long long ll;

int N;
ll M;
ll a[47], v[MAX_N], res;
int Log[MAX_N];

inline ll read () {
    ll x = 0;
    char c = getchar();
    while (c < '0' || '9' < c)
        c = getchar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    return x;
}

int main () {
    scanf("%d", &N);
    M = read();
    for (int i = 1;i <= N; ++i)
        a[i] = read();
    int mid = 1 + N >> 1;
    int t = (1 << mid) - 1;
    for (int i = 0;i <= 20; ++i)
        Log[1 << i] = i;
    for (int i = 0;i <= t; ++i) {
        v[i] = 0;
        for (int s = i; s > 0;) {
            v[i] += a[Log[(s & (-s))] + 1];
            if (v[i] > M) break;
            s &= (~(s & -s));
        } 
    }
    std::sort(v, v + t + 1);
    int t2 = (1 << N - mid) - 1;
    ll val = 0;
    for (int i = 0;i <= t2; ++i) {
        val = 0;
        for (int s = i; s;) {
            val += a[Log[(s & (-s))] + mid + 1];
            if (val > M) break;
            s &= (~(s & (-s)));
        }
        if (val > M) continue;
        res += std::upper_bound(v, v + t + 1, M - val) - v;
    }
    printf("%lld\n", res);
    return 0;
}