SP4580 ABCDEF - ABCDEF

题目传送门

前置芝士：

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

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

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

思路：

首先转化一下题目中的式子：

$$a \times b+c=d \times (e+f)$$

由式子可知：$a \quad b \quad c$ 与 $d \quad e \quad f$ 是互不相干的

所以可以先算出 $a$ 、$b$、$c$，再算 $d$、$e$、$f$ 即可

也就是说，先搜索 $a \times b + c$ 的所有可能结果，然后搜索 $d \times ( e + f )$ 的所有可能结果，最后将两步的结果合起来即可得到答案

坑点：$d=0$

理解了思路，接下来就看代码啦

CODE ：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return x*f;
}//快读优化 
int n,ans,c1,c2,a[105],a1[2000005],a2[2000005],cnt[2000005];
signed main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) {
    	for(int j=1;j<=n;j++){
    		for(int k=1;k<=n;k++){
    			c1++;
    			a1[c1]=a[i]*a[j]+a[k];//枚举 a b c 
			}
		}
	}
    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){//注意特判 
    				c2++;
    				a2[c2]=a[i]*(a[j]+a[k]);//枚举 d e f 
				}
			}
		}
	}
    sort(a1+1,a1+c1+1),sort(a2+1,a2+c2+1);
    for(int i=1,j=1;i<=c2;i++){
        if(i!=1&&a2[i]==a2[i-1]){
			cnt[i]=cnt[i-1];
			continue;
		}
        while(a1[j]<=a2[i]&&j<=c1){
            if(a1[j]==a2[i])cnt[i]++;
            j++;
        }
    }
    for(int i=1;i<=c2;i++)ans+=cnt[i];
    cout<<ans<<endl;
    return 0;
}