折半搜索

meet in the middle 算法 （又叫 split and merge 算法）

顾名思义这种算法就是同时从两个点往中间搜索，直到碰头为止

而使等式两边未知数个数相等或尽量均匀分布是用 meet in the middle 算法解决等式问题的常见方法

SP4580 ABCDEF

题目描述

给定一个集合S（元素个数100以内）
求满足下式的六元组个数

解题思路

将等式化简得到

a*b+c=d*(e+f)

可以看出两边互不相干，分别求出等式两边的所有情况，再进行折半搜索

#include<bits/stdc++.h>

using namespace std ;

int n ;
long long  num[101] ;
long long Lpart[1000001],Rpart[1000001] ;
long long ans = 0 ;
int main()
{
    scanf("%d",&n) ;
    for(int i=1;i<=n;++i) scanf("%lld",&num[i]) ;
    int cnt=0 ;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                Lpart[++cnt] = num[i]*num[j]+num[k] ;
    cnt=0 ;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
            {
                Rpart[++cnt] = num[i]*(num[j]+num[k]) ;
                if(num[i]==0) Rpart[cnt]=LONG_LONG_MAX ;
            }
                
    sort(Lpart+1,Lpart+1+n*n*n) ;
    sort(Rpart+1,Rpart+1+n*n*n) ;
    int i=n*n*n ;
    int j=n*n*n ;

    for(;i>=1&&j>=1;)
    {
        long long now = 0 ;
        for(;j>=1;)
        {
            if(Rpart[j]==Lpart[i]) now++ ;
            if(Lpart[i]-Rpart[j]>0) break ;
            j-- ;
        }
        ans+=now ;
        for(;;)
        {
            i-- ;
            if(i<1) break ;
            if(Lpart[i]==Lpart[i+1]) ans+=now ;
            else break ;
        }
    }
   
    printf("%lld",ans) ;
    return 0 ;
}

其他解题思路：

可以直接将等式左边的结果存入hash表，然后用等式右边的结果再hash表中查找