2019牛客暑期多校训练营(第九场)D折半枚举

Description

给出N( <= 36)和一个sum值，给出N个数字，从中选几个和为sum

Analyze

所有数字都有1(选取)、0(不选取)两种选择，所有状态就是2 ^ 36种

枚举所有状态必然超时

我们发现，2 ^ 36，底数为2(0/1两种状态)，幂不超过40而接近40

这些都指向->折半枚举

折半枚举适合的题目：每个数字(物品)只有选取与不选取两种选择，数字(物品)数目不超过40但接近于40(2 ^ 20可遍历)

所以要对 (N <=40 、 N：0/1）敏感，反应出这是折半枚举

Code

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);
#define Debug cout << "-----------------" << '\n';

int n;
ll num, a[40];
bool vis[40];

struct node
{
    vector<int> c;
    ll sum;
    bool operator<(const node g)const
    {
        return sum < g.sum;
    }
} e[1 << 19];
ll e_copy[1 << 19];

int main()
{
    scanf("%d%lld", &n, &num);
    for(int i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    int mid = n / 2;
    for(int i = 0; i < (1 << mid); ++i)
    {
        for(int j = 0; j < mid; ++j)
            if(i >> j & 1)
            {
                e[i].c.push_back(j);
                e[i].sum += a[j];
            }
    }

    sort(e, e + (1 << mid));

    int idx = 1;
    for(int i = 1; i < (1 << mid); ++i)
        if(e[i - 1].sum < e[i].sum)
            e_copy[idx++] = e[i].sum;

    node tem;
    int ans;
    for(int i = 0; i < 1 << (n - mid); ++i)
    {
        tem.sum = 0;
        tem.c.clear();
        for(int j = 0; j < n - mid; ++j)
            if(i >> j & 1)
            {
                tem.c.push_back(j);
                tem.sum += a[j + mid];
            }
        if(tem.sum <= num)
        {
            int pos = lower_bound(e_copy, e_copy + idx, num - tem.sum) - e_copy;
            if(pos != (1 << mid) && e_copy[pos] + tem.sum == num)
            {
                ans = pos;
                break;
            }
        }
    }
    int sz = tem.c.size();
    for(int i = 0; i < sz; ++i)
        vis[ tem.c[i] + mid ] = 1;

    sz = e[ans].c.size();
    for(int i = 0; i < sz; ++i)
        vis[ e[ans].c[i] ] = 1;

    for(int i = 0; i < n; ++i)
        if(vis[i])
            cout << '1';
        else
            cout << '0';
    cout << '\n';
    return 0;
}

Code of TLE（DFS暴搜）

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define eps 1e-8
#define PI acos(-1.0)
#define ll long long
using namespace std;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
#define Close ios::sync_with_stdio(false);
#define Debug cout << "-----------------" << '\n';

int n, cnt = -1;
bool vis[40], flag;
ll sum, a[40];

void DFS(ll rest)
{
    cnt++;
    if(rest == 0 || flag == 1)
    {
        flag = 1;
        cnt--;
        return ;
    }
    if(cnt >= n || rest < 0)
    {
        cnt--;
        return ;
    }

    vis[cnt] = 1;
    rest -= a[cnt];
    DFS(rest);
    if(flag)
    {
        cnt--;
        return ;
    }

    vis[cnt] = 0;
    rest += a[cnt];
    DFS(rest);
    cnt--;
}


int main()
{
    scanf("%d%lld", &n, &sum);
    for(int i = 0; i < n; ++i)
        scanf("%lld", &a[i]);
    flag = 0;
    memset(vis, 0, sizeof(vis));
    ll rest = sum;
    DFS(rest);
    for(int i = 0; i < n; ++i)
        if(vis[i])
            cout << '1';
        else
            cout << '0';
    cout << '\n';
    return 0;
}