折半枚举

折半枚举是一种很好用的枚举方法，比如有时集合过大无法全部搜索，但刚好只需要他们的和或其他可以处理出的东西，就可以一半一半搜

---

题1

4 Values whose Sum is 0 传送门：POJ2785 此题就是要求 a+b+c+d=0 的个数 那么 a+b=-(c+d) 只与和有关，所以先把 c+d 的和预处理并排序，当 a+b 值一定时，显然 c+d 值也一定，所以只要二分出 满足c+d=-(a+b) 的 c+d 的个数即可 很容易的样子 以下代码

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

#define LL long long

int n,ans;;
int a[4005],b[4005],c[4005],d[4005],f[16000005];

int main(){
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			f[(i-1)*n+j]=c[i]+d[j];
	sort(f+1,f+n*n+1);
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++){
			int F=-(a[i]+b[j]);
			ans+=upper_bound(f+1,f+n*n+1,F)-lower_bound(f+1,f+n*n+1,F);
		}
		
	cout<<ans;
	return 0;
}

---

题2 （NOIP PJ 的题目）

传送门：CodeVS5624 可以算是一个折半枚举吧 显然一次处理完$x_a,x_b,x_c,x_d$时间不支持 用 $ans^{xy}$记录 数x（注意不是第x个）在位置y上出现的次数 那么枚举差值 i ， 再枚举 $x_a$ 则 ： $x_b=x_a+i*2;$ $x_c>x_b+i*6=x_a+i*8;$ $x_d=x_c+i;$ 换句话说 $x_b$ 已确定下来 然后再来研究一下 $x_c,x_d$ 当 $x_c$ 确定下来后，$x_d$ 也确定下来 并且随着 $x_a$ 的增大 $x_c$ 的范围单调递减（反过来就是随着 $x_a$ 的增大，$x_c$ 的范围单调递增） 于是就可以利用这一性质求出 $sum=\sum(f[x_c]*f[x_d])$ 然后就能累加到 $ans_{x_a1} 和 ans_{x_b2}$ 上 同理累加 $ans_{x_c3} 和 ans_{x_d4}$

所以核心就是每次对前两个或后两个利用单调性进行处理

详见代码

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n,m,sum,A,B,C,D,a[40005],f[20005],ans[20005][5];

int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>a[i];
		f[a[i]]++;
	}
	
	for (int i=1;i<=2000;i++){
		sum=0;
		for (A=n-9*i-1;A>=1;A--){
			B=A+2*i; C=A+8*i+1; D=A+9*i+1;
			sum+=f[C]*f[D];
			ans[A][1]+=f[B]*sum;
			ans[B][2]+=f[A]*sum;
			
		}
		sum=0;
		for (C=2+8*i;C<=n;C++){
			A=C-8*i-1; B=C-6*i-1; D=C+i;
			sum+=f[A]*f[B];
			ans[C][3]+=f[D]*sum;
			ans[D][4]+=f[C]*sum;
			
		}
	}
	
	for (int i=1;i<=m;i++) 
		cout<<ans[a[i]][1]<<' '<<ans[a[i]][2]<<' '<<ans[a[i]][3]<<' '<<ans[a[i]][4]<<'\n';
	
	return 0;
}