2024SMUSpring天梯4补题

L2-3:用扑克牌计算24点

题意:

思路：全排列枚举 or dfs得到全排列。枚举方式和"飞机降落"一样。题目类似"电阻组合"那题。要注意的是要枚举3种东西：数字的全排列，符号的全排列，以及！括号的情况！。一开始括号只是考虑到样例那种情况，wa两个点。括号会影响除法的计算。

总的来说：枚举出全排列，符号的情况及组合。进行check即可，check中考虑这种组合情况的不同括号的计算结果。

ps：一定一定要封装成函数，好写很多。

double card[5],vis1[5],vis2[5];
vector<int> vct;
vector<char> opp;
bool res=false;
char op[4]={'+','-','*','/'};
double process(double a,double b,char op){
    if(op=='+') return a+b;
    if(op=='-') return a-b;
    if(op=='*') return a*b;
    if(op=='/'&&b==0) return -99999999999999999;              //实际上b不可能为0，因为b是card中的数
    if(op=='/'&&b!=0) return a/b;
}
void check(){           //括号的情况有五种
    int a=vct[0],b=vct[1],c=vct[2],d=vct[3];
    char op1=opp[0],op2=opp[1],op3=opp[2];
    if( process(process(process(a,b,op1),c,op2),d,op3)==24 ){               //((a^b)^c)^d
        cout<<"(("<<a<<op1<<b<<")"<<op2<<c<<")"<<op3<<d;
        res=true;
    }
    else if( process(process(a,b,op1),process(c,d,op3),op2)==24 ){            //(a^b)^(c^d)
        cout<<"("<<a<<op1<<b<<")"<<op2<<"("<<c<<op3<<d<<")";
        res=true;
    }
    else if( process(process(a,process(b,c,op2),op1),d,op3)==24 ){              //a^(b^c)^d
        cout<<a<<op1<<"("<<b<<op2<<c<<")"<<op3<<d;
        res=true;
    }
    else if( process(a,process(process(b,c,op2),d,op3),op1)==24 ){               //a^((b^c)^d)
        cout<<a<<op1<<"(("<<b<<op2<<c<<")"<<op3<<d<<")";
        res=true;
    }
    else if( process(a,process(b,process(c,d,op3),op2),op1)==24 ){               //a^(b^(c^d))
        cout<<a<<op1<<"("<<b<<op2<<"("<<c<<op3<<d<<"))";
        res=true;
    }
}
void dfs2(){            //符号的全排列
    if(opp.size()==3){
        check();
        return;
    }
    for(int i=0;i<4;i++){       //i<4
        if(vis2[i]) continue;
        vis2[i]=1;
        opp.emplace_back(op[i]);
        dfs2();
        vis2[i]=0;
        opp.pop_back();
        if(res) return;
    }
}
void dfs1(){
    if(vct.size()==4){          //卡牌的全排列情况之一
        dfs2();
        return;
    }
    for(int i=1;i<=4;i++){       //枚举卡牌的全排列的情况
        if(vis1[i]) continue;
        vis1[i]=1;
        vct.emplace_back(card[i]);
        dfs1();
        vis1[i]=0;
        vct.pop_back();
        if(res) return;
    }
}
void solve(){           //L2-3          就是电阻题//枚举数字组合--枚举字符组合--
    // 枚举括号组合--除法的问题，顺序对除法有影响...
    cin>>card[1]>>card[2]>>card[3]>>card[4];
    dfs1();
    if(res==false) cout<<"-1";
}