折半搜索

zhyh · 2021-01-14 11:22:36 · 个人记录

meet in the middle

对于方案数问题的搜索，以选或不选为例，相当于在一定限制的条件下做枚举，所以最坏的复杂度是 O(2^N) ，即傻傻地枚举了所有方案。

做一个图：

我们可以把 N 分成两块，分别做搜索再把方案合并起来
如果能做到高效地合并方案，搜索的复杂度就成功地降下去了,变成 O(2^{\frac{N}{2}}+f(2^{\frac{N}{2}})) ，函数 f 即这个合并的效率

我们发现，这显然得到了两个子问题啊！那我们是不是能再分下去呢！
然而还要考虑合并方案带来的复杂度，由于方案数即为搜索规模量，即使搜索能再降，合并方案的问题仍然卡在那...
如果能够快速合并方案数，那么恭喜你，你很可能在写一棵线段树之类的...至少我开心地写着写着发现...

void mergeSearch(int x, int l, int r)
{
    if (l == r) { if (A[l] <= M) Q[x][++tot[x]] = A[l]; } // Q[x][0] = 0;
    else {
        int mid = (l + r) >> 1;
        mergeSearch(lson, l, mid);
        mergeSearch(rson, mid+1, r);
        sort(Q[lson], Q[lson]+tot[lson]);
        sort(Q[rson], Q[rson]+tot[rson]);
        for (int i=0; i<tot[lson]; i++) {
            for (int j=0; j<tot[rson]; j++) {
                // ???  
            } 
        }
    }
}

这特么不是线段树吗？？！
但合并的问题卡在那，失败。

至少对于带幂的复杂度来说，幂能减半真的漂亮！
模板题：P4799

void dfs(int l, int r, ll sum, int tp)
{
    if (l > r) Q[tp][++tot[tp]] = sum;
    else {
        if (sum + A[l] <= M) dfs(l+1, r, sum+A[l], tp);
        dfs(l+1, r, sum, tp);
    }
}

dfs(1, N>>1, 0, 0);
dfs((N>>1)+1, N, 0, 1);
// 然后是合并的操作
// ...

天平问题：把物品分成两部分，用两座天平秤（状态/权值变成 -1， 0， 1），把两座天平各自称过的所有重量拿去合并