P2277 题解

· · 题解

题意

求有几种方式算出 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);
}
}