题解 SP11469 【SUBSET - Balanced Cow Subsets】

Ofnoname · 2019-10-22 21:05:43 · 题解

SP11469 SUBSET - Balanced Cow Subsets

大家一定是在P3067的推荐里找到这道题的，两道题题面相同，数据范围相同，连样例都一样。但是那道题的代码一般是过不了这道题的，显然可以发现如果折半搜出的两个序列数字都相等的话是会被卡爆的，这是我们就需要更稳更好打的方法。

我们换个角度考虑，N只有区区20，所有选或不选的方案数只有2^N\ = \ 1e6，如果在两次搜索就把每种选的情况可行性做出来，就可以解决问题。

第一次搜索时，我们记录每一种结果可以被哪些组合拼出来（N == 20，组合状态是可以压缩的）。当然一种结果可能被多个组合拼出来，所以要用vector记录，而一个结果也可能很大，需要用map离散化（编个号就行，不用排序）。

那么第二次搜索时，每当我们得到一个结果S，我们是需要前一半产生-S的总和来得到方案的，显然-S的方案就是S的方案反过来而已，是完全等效的，那么我们遍历第一次搜到的所有能使前一半算出S的方案，他们的组合与后一半的组合并在一起就是一个可能的答案。

#include <bits/stdc++.h>
#define MAX (2000000 + 7)
using namespace std;

int N, mx, mc, ans, a[23], use[MAX];

vector <int> d[MAX];
map <int, int> M;

void DFS1(int i, int sum, int now)//now为压缩状态，sum为当前和 
{
    if (i > mx)
    {
        if (!M.count(sum)) M[sum] = ++mc;//（伪）离散化
        d[M[sum]].push_back(now);//当前now可以拼出sum的和 
        return;
    }
    DFS1(i+1, sum, now);
    DFS1(i+1, sum+a[i], now|(1<<(i-1)));
    DFS1(i+1, sum-a[i], now|(1<<(i-1)));
}

void DFS2(int i, int sum, int now)
{
    if (i > N)
    {
        if (M.count(sum))
        {
            int x = M[sum];//寻找前一半能拼出-sum的组合 
            for (int i = 0; i < d[x].size(); i++)
                use[d[x][i] | now] = 1;//两半组合就是一个可能的一个答案 
        }return;
    }
    DFS2(i+1, sum, now);
    DFS2(i+1, sum+a[i], now|(1<<(i-1)));
    DFS2(i+1, sum-a[i], now|(1<<(i-1)));
}

int main()
{
    scanf("%d", &N), mx = N >> 1;
    for (int i = 1; i <= N; i++)
        scanf("%d", a + i);
    DFS1(1, 0, 0), DFS2(mx + 1, 0, 0);
    for (int i = 1; i <= 1<<N; i++)//遍历每一种 
        ans += use[i];
    printf("%d\n", ans);
}