引入
\(1.\text{以经典例题引入：}\)
有一个长度为n的序列a，任选一些数求能组成的小于m的数的方案数(0不算)
\(\quad\text{看完题目第一反应，这不就是裸01背包吗？m为容量}\) \(a_i\text{为价值和体积，轻松AC。}\)
\(\quad\text{我们再来看一下数据范围}\ n\le40\ a_i\le10^9\ m\le4*10^{10}\)
\(\quad\text{额...这}\ m\ \text{大的离谱，总不能定义个 }f\left[40000000000 \right]\)。
\(\quad\text{于是折半搜索就这样出现了。}\)
介绍
\(1.\text{何为折半搜索？}\)
\(\quad\text{故名思义，就是把一个序列从中间分开，分别对两边搜索。}\)
$\quad\text{回到开篇例题，我们将序列}\ n\ \text{分为}1\sim \dfrac{n}{2} \ \text{和\ }\dfrac{n}{2}+1\sim n\ \text{两个序列。} $
\(\quad\text{然后分别搜索，决策为选和不选，将组成的数放入一个数组。}\)
\(\quad\text{这样我们得到两个数组}\ f[ \ ]\ s[\ ]\ \text{分别为两个序列所能组成的数。}\)
\(\quad\text{将}\ f[\ ]\ \text{排序后遍历}\ s[\ ]\ \text{每次循环找到}\ f[\ ]\ \text{中第一个大于}\ m-s_i\ \text{的数。}\)
\(\quad\text{可以使用}upperbound\text{来寻找，加到}\ ans\ \text{就行了。}\)
\(2.\text{时间复杂度}\)
\(\quad\text{因为每次只搜了一半的序列，所以为}\ O(2* 2^{ \frac{n}{2}}+\dfrac{n}{2}* \dfrac{n}{2}log\dfrac{n}{2}+\dfrac{n}{2}log\dfrac{n}{2})(\text{乱算的})\)
\(\quad\text{反正约等于}\ O( 2^{\frac{n}{2}})\)。
\(3.\text{代码}\)
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL n,m,a[50],ans=0;
vector<LL> fi, sc;
inline LL read(){
LL s=0,w=1;char ch;
ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-'){w=-1;}ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
return s*w;
}
void print(LL x){
char F[200];LL cnt=0;
if(x<0) {x=-x;putchar('-');}
if(x==0){putchar('0');putchar('\n');return ;}
while(x){F[++cnt]=x%10;x/=10;}
while(cnt){putchar(F[cnt--]+'0');}
putchar('\n');
return ;
}
void dfs1(int dep,int end,int tot){
if(tot+a[dep]>m){
return;
}
if(dep>end)
return;
fi.push_back(tot + a[dep]);
dfs1(dep + 1, end, tot + a[dep]);
dfs1(dep + 1, end, tot);
return;
}
void dfs2(int dep,int end,int tot){
if(tot+a[dep]>m){
return;
}
if(dep>end)
return;
sc.push_back(tot + a[dep]);
dfs2(dep + 1, end, tot + a[dep]);
dfs2(dep + 1, end, tot);
return;
}
int main(){
n = read(), m = read();
for (int i = 1;i<=n;i++){
a[i] = read();
}
fi.push_back(0);
sc.push_back(0);
dfs1(1, (n >> 2), 0);
dfs2((n >> 2) + 1, n, 0);
sort(fi.begin(), fi.end());
for (vector<LL>::iterator it = sc.begin(); it != sc.end();it++){
vector<LL>::iterator e=upper_bound(fi.begin(),fi.end(),m-*it);
ans += e - fi.begin();
}
print(ans-1);
return 0;
}
\(\quad\text{}\)
习题
\(1.\)P4799 [CEOI2015 Day2]世界冰球锦标赛
\(\quad\text{跟经典例题一样}\)
\(2.\)P3067 [USACO12OPEN]Balanced Cow Subsets
$\ \ $ SP11469 SUBSET - Balanced Cow Subsets
\(\quad\text{每次搜索有三种情况 左边 右边 不选 难点在判重。}\)
\(\quad\text{设前半搜索总和左为}a\ \text{右为b ，后半搜索为左c 右d}\)
\(\quad a+c=b+d \ \Longrightarrow \ a-b=d-c\)
\(\quad\text{可以用位运算和map来判重。}\)