折半搜索学习笔记

xingke233 / 2024-11-09 / 原文

引入

$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{}$