2020年9月7日2020年12月16日 by woshiluo

题目链接: https://loj.ac/problem/2789

给定 m 和一个长度为 n 数列 a

一种方案为从 a 中选择 k(0≤k≤n) 个数字出来（在一个方案中，每一位只能选择一次）

一种合法的方案为选择的所有数字加起来不超过 m

n≤40

一开始是大力搜嘛，毕竟 2n 也不是很大，还是要有梦想的

然后就只有 40pts 了，然后就想背包，发现背包也就 70pts，后面那几个 1016 怎么想都不可能背包

后来发现虽然 240 会爆炸， 220 并不会

那就枚举前一半和后一半，然后合并即可

枚举可以搜索和二进制枚举，但是搜索会快一点（可以剪枝），但是二进制枚举不费脑子，我写的是二进制枚举

合并可以二分或者直接双指针，双指针又快又不费脑子，我写的是双指针

提交链接: https://loj.ac/submission/926831

#include <cstdio>

#include <vector>
#include <algorithm>

const int N = 40;
const int BIT = 22;

int n;
long long m, ans;
long long a[N], sum[N];

inline int full_bit( int k ) { return 1 << k; }
inline int has( int k, int i ) { return ( k >> ( i - 1 ) ) & 1; }

int main() {
    scanf( "%d%lld", &n, &m );
    for( int i = 1; i <= n; i ++ ) {
        scanf( "%lld", &a[i] );
    }
    std::sort( a + 1, a + n + 1 );
    int fir_cnt = n / 2; int sec_cnt = ( n / 2 ) + ( n & 1 );
    std::vector<long long> fir, sec;
    for( int k = 0; k < full_bit(fir_cnt); k ++ ) {
        long long res = 0;
        for( int i = 1; i <= fir_cnt; i ++ ) {
            if( has( k, i ) ) {
                res += a[i];
            }
        }
        if( res <= m ) {
            fir.push_back(res);
        }
    }
    for( int k = 0; k < full_bit(sec_cnt); k ++ ) {
        long long res = 0;
        for( int i = 1; i <= sec_cnt; i ++ ) {
            if( has( k, i ) ) {
                res += a[i + fir_cnt];
            }
        }
        if( res <= m ) {
            sec.push_back(res);
        }
    }
    std::sort( fir.begin(), fir.end() );
    std::sort( sec.begin(), sec.end() );
    int fir_size = fir.size(), sec_size = sec.size();
    int p1 = 0, p2 = sec_size - 1;
    long long ans = 0;
    while( p1 < fir_size && p2 >= 0 ) {
        while( fir[p1] + sec[p2] > m && p2 >= 0 ) {
            p2 --;
        }
        if( p2 < 0 ) {
            break;
        }
        ans += 1LL * ( p2 + 1 );
        p1 ++;
    }
    printf( "%lld\n", ans );
}

class OI

local_offer CEOI local_offer 搜索 local_offer 枚举

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注