自动搬运

查看原文

来自洛谷，原作者为

	yeshubo_qwq 我是 luxu。

搬运于2025-08-24 21:35:52，当前版本为作者最后更新于2021-11-02 20:26:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

求有几种方式算出 $24$ 点。

思路

大致思路：dfs 排列每种情况，再暴力枚举运算符号，最后判断是否算出 $24$ 并去重求出答案。

这里讲一下几个注意点：

1.注意判断实数计算的误差。

2.括号前面是减号、除号，加上括号要变号，因此加上括号后可能与枚举的符号不同。

3.判重可以将先将算式转为后缀表达式，再用状压将后缀表达式转成数，并用 map 去重。

#include<bits/stdc++.h> 
using namespace std;
const double check=1e-6;//实数计算误差
int ans,v[5],pm[5],f[5],g[5];
map<int,int> mp;
double num(double x,double y,int z){//计算
	switch(z){//z表示运算符：0加，1减，2乘，3除
		case 0:return x+y; break;
		case 1:return x-y; break;
		case 2:return x*y; break;
		case 3:return x/y; break;
	}
}
double Abs(double p){//实数绝对值
	return (p<0?-p:p);
}
int useful(int a,int b){//能不能加括号
//括号前面是减号、除号，加上括号要变号
	if(a%2==1) return 1;
	if(!a) return (b>1?1:0);
	else return (b<2?1:0);
}
void mplus(int a1,int a2,int a3,int a4,int a5,int a6,int a7){//map+状压去重
	int x=(a1|a2<<3|a3<<6|a4<<9|a5<<12|a6<<15|a7<<18);
    if(++mp[x]==1)ans++;
}
int find(int x){//x是第几个
	for(int i=1;i<=4;i++)
		if(f[i]==x)return i;
}
void count(int a,int b,int c,int d){//暴力计算
	for(int i=0;i<=3;i++)//i,j,k枚举符号
	for(int j=0;j<=3;j++)
	for(int k=0;k<=3;k++){
/*		5种添括号
      	(1,2,3,4)
		((1,2),(3,4))
		(1,(2,3,4))
		((1,(2,3)),4)
		(1,(2,(3,4)))*/
		int u1=useful(k,j), u2=useful(j,i);
		if( Abs((num( num( num(a,b,i) ,c,j),d,k)  -24 ))<check)
			mplus(pm[find(a)],pm[find(b)],(i+4),pm[find(c)],(j+4),pm[find(d)],(k+4));
		if(u1==1&& Abs(num( num(a,b,i),num(c,d,j) , k)   -24 )<check)
			mplus(pm[find(a)],pm[find(b)],(i+4),pm[find(c)],pm[find(d)],(j+4),(k+4));
		if(u1==1&& Abs(num(a,num( num(b,c,i),d,j),k)     -24 )<check)
			mplus(pm[find(a)],pm[find(b)],pm[find(c)],(i+4),pm[find(d)],(j+4),(k+4));
		if(u2==1&& Abs(num(num(a, num(b,c,i) ,j),d,k)    -24 )<check)
			mplus(pm[find(a)],pm[find(b)],pm[find(c)],(i+4),(j+4),pm[find(d)],(k+4));
		if(u1==1&&u2==1&& Abs(num(a, num(b,num(c,d,i),j),k)-24 )<check)
			mplus(pm[find(a)],pm[find(b)],pm[find(c)],pm[find(d)],(i+4),(j+4),(k+4));
	}
}
void dfs(int x){//dfs求排列
	if(x>4){
		count(g[1],g[2],g[3],g[4]);
		return;
	}
	for(int i=1;i<=4;i++)
		if(v[i]==0)
			v[i]=1,g[x]=f[i],dfs(x+1),v[i]=0;
}
int main(){
	for(int i=1;i<=4;i++)scanf("%d",&f[i]);
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
			pm[i]=pm[i]+(f[i]<f[j]?1:0);//排第几，用于状压判重（最大0）
	dfs(1);
	printf("%d",ans);
}
}