前置知识
搜索。
引入
我们知道，暴力搜索的复杂度往往是指数级的，这在数据范围稍微大一点的情况下就难以承受。而双向搜索可以通过一些方法对搜索进行优化。本文介绍两种双向搜索——双向同时搜索和 Meet in the Middle。
双向同时搜索
双向同时搜索一般可以应用在起点和终点是确定的，操作可逆的情况，例如马走日和八数码问题。
双向同时搜索，顾名思义，就是从起点和终点同时搜索，一旦两条搜索的路径有了交点，就表示找到了一条从起点通往终点的路径。
在八数码问题（Luogu P1379）中，一种简单的搜索就是使用 BFS，将起点加入到队列中，然后依次向下扩展。这样做是可以 AC 的，但是很慢，因为状态数很多。
int bfs()//单向搜索，用时 10.15s，内存 16.90MB。
{
if (st==ed) return 0;
q.push(st);
bj[st]=1;
f[st]=0;
while (!q.empty())
{
int now=q.front(),x,y;q.pop();
for (int i=3;i;--i)
for (int j=3;j;--j)
{
a[i][j]=now%10,now/=10;
if (a[i][j]==0) x=i,y=j;
}
for (int i=1;i<=3;++i)
for (int j=1;j<=3;++j)
now=now*10+a[i][j];
if (now==ed) return f[now];
for (int k=1;k<=4;++k)
{
int xx=x+fx[k],yy=y+fy[k];
if (xx<1||xx>3||yy<1||yy>3) continue;
swap(a[x][y],a[xx][yy]);
int nxt=0;
for (int i=1;i<=3;++i)
for (int j=1;j<=3;++j)
nxt=nxt*10+a[i][j];
if (bj[nxt]) {swap(a[x][y],a[xx][yy]);continue;}
f[nxt]=f[now]+1;
bj[nxt]=bj[now];
q.push(nxt);
swap(a[x][y],a[xx][yy]);
}
}
return -1;
}
那么如何加速呢。很显然可以利用双向同时搜索。我们将起点和终点同时加入到队列中，打上不同的标记。那么在搜索的过程中，一旦搜索到与当前点不同的标记，就说明两条路径相交了，那么意味着一条从起点到终点的路径被找到了，也就得到答案了。
int bfs()//双向同时搜索，用时 281ms，内存 1.07MB。
{
if (st==ed) return 0;
q.push(st);q.push(ed);//起点终点都加入到队列中
bj[st]=1;bj[ed]=2;
f[st]=0;f[ed]=0;
while (!q.empty())
{
int now=q.front(),x,y;q.pop();
for (int i=3;i;--i)
for (int j=3;j;--j)
{
a[i][j]=now%10,now/=10;
if (a[i][j]==0) x=i,y=j;
}
for (int i=1;i<=3;++i)
for (int j=1;j<=3;++j)
now=now*10+a[i][j];
for (int k=1;k<=4;++k)
{
int xx=x+fx[k],yy=y+fy[k];
if (xx<1||xx>3||yy<1||yy>3) continue;
swap(a[x][y],a[xx][yy]);
int nxt=0;
for (int i=1;i<=3;++i)
for (int j=1;j<=3;++j)
nxt=nxt*10+a[i][j];
if (bj[nxt])
{
if (bj[nxt]==bj[now]) {swap(a[x][y],a[xx][yy]);continue;}
else return f[now]+f[nxt]+1;//搜到不一样的标记就得到了答案。
}
f[nxt]=f[now]+1;
bj[nxt]=bj[now];
q.push(nxt);
swap(a[x][y],a[xx][yy]);
}
}
return -1;
}
可以看到，双向搜索的用时和内存都远远小于单向搜索，这是因为减小了无用的状态数。这也就是双向同时搜索带来的优化。
Meet in the Middle
我一般将 Meet in the Middle 翻译为折半搜索，这和二分搜索是不一样。这里的折半指的是将数据分割，各自独立搜索，然后计算答案。
下面以几道题来详细的到底什么是分组独立搜索。
例题
SP4580 ABCDEF - ABCDEF
有一种显然的想法就是暴力枚举 a,b,c,d,e,f，然后判断是否符合题意。时间复杂度是 \(\mathcal O(V^6)\)，也就是 \(\mathcal O(10^{12})\)，是难以承受的。
但是我们可以对式子进行变形。
至此，我们将 a,b,c 和 d,e,f 分成了两组，我们对这两组分别搜索，将所有可能的值各自统计，然后有双指针查找其中相同的值。时间复杂度直接降到了 \(\mathcal O(2*V^3)\)，这已经是可以接受的了。
从中可以看出，分组独立搜索是基于待搜索的每个元素间没有联系，从而保证分组的可行性。独立搜索后，再使用一些方法将每个组的答案合并。一般来说，我们会将元素分成两组，然后用双指针来合并答案。
#include<cstdio>
#include<algorithm>
#define N 1000005
using namespace std;
int n,num1,num2,ans,a[N],a1[N],a2[N],cnt[N];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
for (int k=1;k<=n;++k)
a1[++num1]=a[i]*a[j]+a[k];
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
for (int k=1;k<=n;++k)
if (a[i]!=0)//注意 d≠0
a2[++num2]=(a[j]+a[k])*a[i];
sort(a1+1,a1+num1+1);sort(a2+1,a2+num2+1);
for (int i=1,j=1;i<=num2;++i)
{
if (i!=1&&a2[i]==a2[i-1]) {cnt[i]=cnt[i-1];continue;}
while (j<=num1&&a2[i]>=a1[j])
{
if (a2[i]==a1[j]) cnt[i]++;
++j;
}
}
for (int i=1;i<=num2;++i)
ans+=cnt[i];
printf("%d\n",ans);
return 0;
}