20251103折半搜索总结

引子

折半搜索（又称meet-in-the-middle）是一种优化搜索算法的方法。其说白了就是将搜索过程分成两个部分：先分别对两部分进行独立搜索，得到两个结果序列，最后通过合并这两个序列得到答案。

由于搜索算法的时间复杂度通常为指数级，当n较大时容易导致超时。采用折半搜索后，时间复杂度可由O(2n)O(2^n)O(2n)降到O(2n2+1)O(2^{\frac{n}{2}+1})O(22n​+1)。

C P4799 世界冰球锦标赛

折半搜索模板为何放在放在第三题？

这题就先折半搜索，接着合并时，我们可以先将一部分进行排列使其有序，然后遍历另一部分，每次进行二分搜索查找可行的答案，最后叠加可行方案数。

#include<bits/stdc++.h>usingnamespacestd;intn;longlongm,a[45];vector<longlong>a1,a2;voiddfs1(intk,longlongsum){if(sum>m)return;if(k>n/2){a1.push_back(sum);return;}dfs1(k+1,sum+a[k]);dfs1(k+1,sum);}longlongans=0;voiddfs2(intk,longlongsum){if(sum>m)return;if(k>n){a2.push_back(sum);return;}dfs2(k+1,sum+a[k]);dfs2(k+1,sum);}intmain(){cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i];}dfs1(1,0);dfs2(n/2+1,0);sort(a2.begin(),a2.end());for(autoi:a1){intp=upper_bound(a2.begin(),a2.end(),m-i)-a2.begin();ans+=p;}cout<<ans;return0;}