折半搜索 学习笔记

· · 题解

之前一直以为折半类型是很难的算法，今天也来尝试一波。

1.概述

折半搜索，又称meet in the middle，通常是把不能直接做的题目分成两半。

把这两半分别搜索。

比如O(2^n)的做法，有时可以分解为O(2*2^{\frac n 2})，但是要考虑合并的复杂度。

合并时可以通过排序，使一部分有序，再通过二分或其他做法合并答案。

其实折半状压也是运用类似的思想。

可以解决一些统计方案，但爆搜会T的题目

2.例题

P4799 [CEOI2015 Day2]世界冰球锦标赛

Bobek有M元钱，共有N场比赛，每场比赛的门票都有一个价格 。 问在总票价不超过M元钱的情况下，Bobek共有多少种不同的观赛方案。 注1：若方案1中观看了某场比赛，方案2中未观看该场，则认为两种方案不同。 注2： 。

折半搜索模板。

只需要拆成两部分，二分查找合适的就行。

注意相等的可以取，所以要用upper_bound查找，数量减一。

但因为vector的下标从0开始，所以就不用了。

Code：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long
vector<int> a, b;
int n, m, A[59], ans;
inline void dfs(int l, int r, int sum, bool sign)
{
    if (sum > m)
        return;
    if (l > r)
    {
        if (!sign)
            a.push_back(sum);
        else
            b.push_back(sum);
        return;
    }
    dfs(l + 1, r, sum + A[l], sign);
    dfs(l + 1, r, sum, sign);
}

signed main()
{
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &A[i]);
    dfs(1, n / 2, 0, 0);
    dfs(n / 2 + 1, n, 0, 1);
    sort(a.begin(), a.end());
    for (int i = 0; i < b.size(); i++)
        ans += upper_bound(a.begin(), a.end(), m - b[i]) - a.begin();
    printf("%lld", ans);
    return 0;
}