Meet In The Middle （MITM） 学习笔记

· · 个人记录

是什么

Meet In The Middle，又称折半搜索，是一种搜索的优化版本，其思想在于把搜索的东西分成两半，分别搜索，再合并，以达到降低时间复杂度的效果。效果如下： 写成数学语言就是

\text{正常的搜索时间复杂度为}O(a^{n}) \text{折半搜索将搜索范围折半，时间复杂度为}O(a^{n/2}+a^{n/2}+\text{合并的时间})

从中可以看出，折半搜索范围（指数）较大（比普通搜索大），方案（底数）也较大且可以分割成两部分的搜索题。

如何实现

我们进行两遍搜索，第一次搜索前半部分，第二次搜索后半部分。
搜索前半部分时，将搜索结束后的答案加入map或者hash一下存储起来。
搜索后半部分时，再与之前储存的答案查找，进行合并。

很简单，是不是，那么现在就拿几道题练练手吧！

题目练习

1.[ISOJ 1516] ABCDEF

题目描述

给出一个集合S(S\in[-30000,30000]),S中有N个互不相同的整数。 要求找到六元组(a,b,c,d,e,f)使得(a\times b+c)\div d-e=f 的六元组个数

题目思路

一道模板题，先考虑把上面的式子变形为 a\times b+c=(f+e)\times d 我们能发现等式两边各自分为两个独立的部分，考虑将 a,b,c 与 d,e,f 分别枚举，再将结果相等的三元组统计答案即可。

code

见附录c1

2. [ISOJ 1517 P5691]方程的解数

题目描述

已知一个n元高次方程：

k_1x^ {p_1}+k_2x^ {p_2}+k_3x^ {p_3}+\dots+k_nx^ {p_n}=0

假设未知数 1\leq x_i \leq M \leq 150,1\leq N\leq 6 ，求这个方程的整数解的个数。

题目思路

另一道模板题，在洛谷上也是。 先看题，若是直接进行DFS的话O(150^6)绝对超时，因此，如果将方程分为两部分分别寻找，那么时间复杂度为O(2\times 150^3)不超时。但是需要注意，方程分为两半后为k_1x^ {p_1}+k_2x^ {p_2}+\dots+k_{n/2}x^{p_{n/2}}=-(k_{n/2+1}x^{p_{n/2+1}}+\dots+k_nx^{p_n}) 因此需转为负数。

code

见附录C2

3. [ISOJ 1519] 均等集合

题目描述

给出N(1\leq N\leq 20)个数，在其中选若干个数，如果这几个数可以分成两个和相等的集合，那么方案数加1。求总方案数。

题目思路

首想分成两部分，但是发现不能直接分，因为左右部分可以互相选择（即左边选右边，右边选左边）。 这时，依旧可以尝试步骤搜索。当选择到a集合时数字加，选至b集合时数字减，则有代码：

dfs1(now+1,x+a[now],y|(1<<(now-1)));\\选至A集合
dfs1(now+1,x-a[now],y|(1<<(now-1)));\\选至B集合
dfs1(now+1,x,y);\\不选

而当统计答案时为了保证不重复，我们采用状态压缩的方法,不会状态压缩的同学来[这里]()（先咕了，先感性理解一下吧）（见代码）。

code

这里给出代码

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,y,z) for(int x=y;x>=z;x--)

using namespace std;

typedef long long ll;
typedef const int ci;
typedef double dou;

int n,a[30],ans,t[2000000],tot,N;
vector<int> v[2000000];
map<int,int> b;
void dfs1(int now,int x,int y)
{
    if(now>N)
    {
        if(b[x]==0)
            b[x]=++tot;
        v[b[x]].push_back(y);
        return ;
    }
    dfs1(now+1,x+a[now],y|(1<<(now-1)));
    dfs1(now+1,x-a[now],y|(1<<(now-1)));
    dfs1(now+1,x,y);
}
void dfs2(int now,int x,int y)
{
    if(now>n)
    {
        int c=b[x];
        if(c)
        {
            _F(i,0,v[c].size()-1)
            {
                t[v[c][i]|y]=1;
            }
        }
        return ;
    }
    dfs2(now+1,x+a[now],y|(1<<(now-1)));
    dfs2(now+1,x-a[now],y|(1<<(now-1)));
    dfs2(now+1,x,y);
}
int main()
{
    scanf("%d",&n);
    _F(i,1,n)
    {
        scanf("%d",&a[i]);
    }
    N=n>>1;
    dfs1(1,0,0);
    dfs2(N+1,0,0);
    _F(i,1,(1<<n))
        if(t[i])
            ans++;
   110 printf("%d",ans);
    return 0;
}

5. [ISOJ 1520 P3154] 循环赛

题目描述

n支队伍踢足球循环赛，每两支队伍刚好打一场比赛。平局时各得1分，而如果有胜负之时，胜者得3分，败者得0分。假设所有的比赛都已经踢完了，给出n支队伍的最终得分，请你统计有多少种可能的分数表。

题目思路

懒得写了，直接看代码理解吧，实在不行看题解。

code

#include <bits/stdc++.h>
#define _F(x,y,z) for(int x=y;x<=z;x++)
#define F_(x,y,z) for(int x=y;x>=z;x--)

using namespace std;

typedef long long ll;
typedef const int ci;
typedef double dou;
ci maxn=4782969;
int n,m,a[10],xr[30],yr[30],lcnt,rcnt,tot,ans,lim1,lim2;
ll l[maxn+10],r[maxn+10],o;
ll ten[20] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000};
ll win(int x){return 3ll*ten[(x-1)<<1];}
ll no(int x,int y){return ten[(x-1)<<1]+ten[(y-1)<<1];}
int get(ll num,int x){return num/ten[(x-1)<<1]%100;}
void dfs1(int now,ll num)
{
    int x=xr[now],y=yr[now];
    int xx=get(num,x),yy=get(num,y);
    ll wx=num+win(x),wy=num+win(y),wn=num+no(x,y);
    if(now<lim1)
    {
        if(xx+3<=a[x])
            dfs1(now+1,wx);
        if(yy+3<=a[y])
            dfs1(now+1,wy);
        if(xx+1<=a[x]&&yy+1<=a[y])
            dfs1(now+1,wn);
    }
    else
    {
        if(xx+3<=a[x])
            l[++lcnt]=wx;
        if(yy+3<=a[y])
            l[++lcnt]=wy;
        if(xx+1<=a[x]&&yy+1<=a[y]) 
            l[++lcnt]=wn;
    }
}
void dfs2(int now,ll num)
{
    int x=xr[now],y=yr[now];
    int xx=get(num,x),yy=get(num,y);
    ll wx=num+win(x),wy=num+win(y),wn=num+no(x,y);
    if(now<lim2)
    {
        if(xx+3<=a[x])
            dfs2(now+1,wx);
        if(yy+3<=a[y])
            dfs2(now+1,wy);
        if(xx+1<=a[x]&&yy+1<=a[y])
            dfs2(now+1,wn);
    }
    else
    {
        if(xx+3<=a[x])
            r[++rcnt]=wx;
        if(yy+3<=a[y])
            r[++rcnt]=wy;
        if(xx+1<=a[x]&&yy+1<=a[y])
            r[++rcnt]=wn;
    }
}
int main()
{
    scanf("%d",&n);
    _F(i,1,n)
        scanf("%d",&a[i]);
    m=(n*(n-1))>>1;
    lim1=m>>1;
    lim2=m;
    for (int i=1;i<=n;i++)
    {
        for (int j=i+1;j<=n;j++)
        {
            xr[++tot]=i;
            yr[tot]=j;
        }
    }
    dfs1(1,0);
    dfs2((m>>1)+1,0);
    F_(i,n,1)
    {
        o=o*100+a[i];
    }
    sort(r+1,r+1+rcnt);
    _F(i,1,lcnt)
    {
        ll t=o-l[i];
        pair<long long *, long long *> res = equal_range(r + 1, r + rcnt + 1, t);
        ans += res.second - res.first;
//      printf("%d ",ans);
    }
    printf("%d",ans);
    return 0;
}

完结撒花！

附录