折半搜索——另类的二分法

折半搜索

前置知识

笼统的二分
\(dfs\)
清醒的头脑

思路

对于一些很暴力的爆搜，我们发现如果使用通常的搜索会炸。会发现，我们通常的搜索有很多状态是冗余的根本不可能实现的，但是又不得不去搜索，所以说，整体二分可以使这些无法实现的冗余状态少搜一点。

\(\color{Fuchsia}{同时，整体二分之后，对于之后的更快的搜索才是更重要的，而不是整体二分的过程。}\)

网上找到一个好图

典型例题

传送门

洛谷 P4799 [CEOI2015 Day2]世界冰球锦标赛

作为一道普及组入门题，我也觉得不过分，但是再看一眼数据 \(N \leq 40\) ，众所周知，这题普通的爆搜时间复杂度是 \(\mathbf{O}(2^N)\) ，明显是不行的，那么应该怎么做呢？

他这个题是要求，选出一些数，然后他们的总和不可以超过 \(M\) ，挺套路的二分。

我现在把他分成两堆数，比如说样例的 \(100\quad1500\quad500\quad500\quad1000\)

现在就变成了

\(100\quad1500\)
\(500\quad500\quad1000\)

那分成这样有什么用呢？
我现在对每一堆数据分别做 \(\mathbf{O}(2^N)\) 的爆搜，然后找出他们可以组成多少钱的门票。
对于第二堆数排序。
然后对第一堆数一个一个的分析，二分在第二堆数中找到恰好合法的那个地方，前面的必定全部合法，那么这题就挺简单了啦。

#include 
#define debug puts("I ak IOI several times");
#define pb push_back
#define int long long
using namespace std;
template inline void read(T& t){
    t=0; register char ch=getchar(); register int fflag=1;
    while(!('0'<=ch&&ch<='9')){if(ch=='-') fflag=-1;ch=getchar();}
    while(('0'<=ch&&ch<='9')){t=((t<<1)+(t<<3))+ch-'0'; ch=getchar();} t*=fflag;
}
template  inline void read(T& t, Args&... args){
    read(t);read(args...);
}
template inline void write(T x){
    if(x<0) putchar('-'),x=~(x-1); int s[40],top=0;
    while(x) s[++top]=x%10,x/=10; if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}
long long n,a[50],b[50],na,nb;
long long posa[1<<21],posb[1<<21],m;
long long cnta,cntb;
void dfs1(long long dep,long long sum){
	if(dep>na){
		posa[++cnta]=sum;
		return;
	}
	dfs1(dep+1,sum+a[dep]);
	dfs1(dep+1,sum);
}
void dfs2(long long dep,long long sum){
	if(dep>nb){
		posb[++cntb]=sum;
		return;
	}
	dfs2(dep+1,sum+b[dep]);
	dfs2(dep+1,sum);
}
#undef int
int main(){
	
#define int long long
	read(n,m);
	na=(n+1)/2;nb=n/2;
	for(int i=1;i<=na;++i) read(a[i]);
	for(int i=1;i<=nb;++i) read(b[i]);
	dfs1(1,0);
	dfs2(1,0);
	//sort(posa+1,posa+cnta+1);
	sort(posb+1,posb+cntb+1);
	int ans=0;
	for(int i=1;i<=cnta;++i)
		ans+=(upper_bound(posb+1,posb+cntb+1,m-posa[i])-posb-1);
	cout<