洛谷P4799 [CEOI2015 Day2] 世界冰球锦标赛 题解

题目链接：P4799 [CEOI2015 Day2] 世界冰球锦标赛

题意：

译自 CEOI2015 Day2 T1「Ice Hockey World Championship」

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格，他不是任何团队的粉丝，也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱，他会去看所有的比赛。不幸的是，他的财产十分有限，他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价，试求：如果总票价不超过预算，他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看，则认为这两种方案不同。

数据组号	\(1-2\)	\(3-4\)	\(5-7\)	\(8-10\)
\(N \leq\)	\(10\)	\(20\)	\(40\)	\(40\)
\(M \leq\)	\(10^6\)	\(10^{18}\)	\(10^6\)	\(10^{18}\)

首先这个 \(20\) 就很有趣 显然暴搜是吧

那么 \(40\) 的情况怎么处理呢

考虑折半搜索。

折半搜索的思想就是

把原来的问题拆分成两部分分别暴搜

然后合并两个部分的答案

显然折半搜索的优劣取决于合并的复杂度

在这题里，我们分别搜前半部分和后半部分

合并的话，直接看代码

dfs(1,mid,0,sum1,cnt1);
dfs(mid+1,n,0,sum2,cnt2);
sort(sum2+1,sum2+1+cnt2);
for(int i=1; i<=cnt1; i++)
    res+=upper_bound(sum2+1,sum2+1+cnt2,m-sum1[i])-sum2-1;
cout << res << '\n';

这里的 \(\tt{upper\_bound}\) 其实很好理解

就是严格大于 \(m-s_1\) 的那个 \(s_2\) 的位置

显然那个 \(s_2\) 之前的都可以取

时间复杂度 \(O(2^{\frac{n}{2}} \log 2^{\frac{n}{2}}) \approx O(n2^{\frac{n}{2}})\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)((1<<20)+15)

int n,m,res,cnt1,cnt2,val[N],sum1[N],sum2[N];
void dfs(int l,int r,int sum,int a[],int &cnt)
{
    if(sum>m) return;
    if(l>r)
    {
        a[++cnt]=sum;
        return;
    }
    dfs(l+1,r,sum+val[l],a,cnt);
    dfs(l+1,r,sum,a,cnt);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> val[i];
    int mid=n/2;
    dfs(1,mid,0,sum1,cnt1);
    dfs(mid+1,n,0,sum2,cnt2);
    sort(sum2+1,sum2+1+cnt2);
    for(int i=1; i<=cnt1; i++)
        res+=upper_bound(sum2+1,sum2+1+cnt2,m-sum1[i])-sum2-1;
    cout << res << '\n';
    return 0;
}