双向广搜->奶牛集合(洛谷p3067)-526互联

题意：给一个n个数字的集合，问集合中有多少个子集满足后面的条件。其中条件是该集合可以分为两个独立子集，这两个子集的和相等。

分析：第一种思路是枚举所有的集合，然后对每个集合进行暴力枚举，时间复杂度O(1 << 40)得分45。
第二种思路是枚举所有的集合，然后对集合元素求和，转01背包问题，时间复杂度也巨高，得分35。
第三种思路是利用双向广搜的思想，降低搜索的层数。把最初的集合分为左右两个子集，然后直接对子集进行暴力搜索，时间复杂度(1 << 20)，得分100。

    /*
根据双向广搜的理念，当搜索是幂次方级别扩散的时候，我们可以从终点和起点同时搜索，尽可能让扩散的层数最小，从而达到降低时间复杂度的效果。

*/

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for(auto& x : a){
        cin >> x;
    }

    int m = n / 2;
    map<int, int> mapp;
    int cnt = 1;
    map<int, vector<int>> sets;
    vector<bool> ans(1 << n);

    function<void(int, int, int, int, int)> dfs = [&](int idx, int p, int sum, int mask, int state){
        if (idx == p){
            if (!mapp.count(sum)){
                mapp[sum] = cnt ++;
            }
            int value = mapp[sum];
            if (state & 1){
                for (const auto& x : sets[value]){
                    ans[mask | x] = 1;
                }
            }
            else{
                sets[value].emplace_back(mask);
            }
            return;
        }
        dfs(idx + 1, p, sum + a[idx], mask | (1 << (idx)), state);
        dfs(idx + 1, p, sum - a[idx], mask | (1 << (idx)), state);
        dfs(idx + 1, p, sum, mask, state);
    };

    dfs(0, m, 0, 0, 0);
    dfs(m, n, 0, 0, 1);
    
    //+1是为了去除两个集合都为空的情况
    cout << (count_if(ans.begin() + 1, ans.end(), [&](int x){return x == true;})) << '\n';
}

奶牛