普及+T7 奶牛 题解

[郑岱钦]

题目

题解

可以发现奶牛只有三种去处：
1.去 A 组
2.去 B 组
3.哪也不去
所以暴力直接计算，但时间复杂度可达 3^{20} ,远远超过 10^7
这时可以想到一种方法：折半搜索
每次枚举前一半和后一半，再组和。
但为了维护方便，我们把式子移个项，
设前一半中 A 组的个数为 a_l ，B 组为 b_l ，后半 A 组为 a_r ， B 组为 b_r
则

a_l+a_r=b_l+b_r\\ =>a_l-b_l=a_r-b_r

所以这样在dfs中我们有三种情况：
1.直接将 i 加1，表示不选
2.将 i 加入 A 中
3.将 i 加入 B 中
依我们上面推出的式子，若选择2，将当前和 +a_i ，否则减去
但储存每种方案太费时间/空间了
所以可以想到状态压缩：
设二进制数 tot 第 i-1 位为 1 表示这个数被选了
然后如果结束时和 =cnt 开一个 map<int,vector<int> > ，将 tot 加入 map_{cnt}
最后在第二次dfs中，将一个表示完成的 ok 数组中所有 map_{cnt} | tot 设为一
为什么是这个奇怪式子？
因为这样可以完整合并每个状态选与不选两种状态（^也可以，因为这两种待合并状态没有交）
最后遍历一遍 ok ，统计答案就好了
some code:

void dfs(int now, int cnt, int tot)
{
    if (now > (n >> 1))
    {
        mp[cnt].push_back(tot);
        return;
    }
    dfs(now + 1, cnt, tot);
    dfs(now + 1, cnt + a[now], tot ^ 1 << now - 1);
    dfs(now + 1, cnt - a[now], tot ^ 1 << now - 1);
}
void dfs2(int now, int cnt, int tot)
{
    if (now > n)
    {
        if (mp[cnt].empty())
            return;
        for (int i = 0; i < mp[cnt].size(); i++)
            ok[tot | mp[cnt][i]] = 1;
        return;
    }
    dfs2(now + 1, cnt, tot);
    dfs2(now + 1, cnt + a[now], tot ^ 1 << now - 1);
    dfs2(now + 1, cnt - a[now], tot ^ 1 << now - 1);
}