「题解」P1834 速算问题

孤芒星河233 · 2022-05-26 20:03:31 · 题解

P1834 速算问题

洛谷原题面

题意

给定4个1~9的整数，通过括号和加、减、乘、除使结果为24，过程中不允许出现分数。输出时需要将每一步运算的括号补齐，并输出字典序最小的一个

思路

不知道其他题解怎么写这么多 四个数，三个填入运算符的位置，四个运算符，甚至可以直接全排列，现在问题就在字典序上面了。通过查阅 ASCII 码，我们知道字典序优先级为 ( , ) , * , + , - , / , 1 ~ 9 。同时对于确定位置的四个数 a,b,c,d ，很明显有以下三种运算顺序

全排列时，第三种情况等同于第一种情况。

于是我们可以先对四个数字排序，然后对于每个填入运算符的位置，按字典序枚举四个运算符。那么我们是否可以在第一种运算顺序成立时输出结果，第一种运算顺序无解时输出第二次运算顺序的第一个解呢？

请看这两个式子 (((2*6)+4)+8) 与 (((2*6)*8)/4) ，很明显后者的 '*' 字典序在前所以后者才是正解，但全排列时应该是前者优先。因此，我们需要把每一个解的字符串存下来，排序后再输出。

代码实现

#include<bits/stdc++.h>
using namespace std;

const int M=114514;
int a[5],ans,x,y,z,xx,yy,zz,cnt;//x,y,z为第一种运算顺序，xx,yy,zz是第二种
char op[5]={' ','*','+','-','/'},str[20];
string s[M];

int operate(int a,int b,char c){//整数a,b,运算符
    if(c=='+') return a+b;
    else if(c=='-') return a-b;
    else if(c=='*') return a*b;
    else{
        if(b==0||a%b!=0) return M;//这样就不用对非法解再处理了
        return a/b;
    }
}

int main(){
    for(int i=1;i<=4;i++) scanf("%d",&a[i]);
    sort(a+1,a+5);
    do{
        for(int i=1;i<=4;i++){
            xx=x=operate(a[1],a[2],op[i]);
            for(int j=1;j<=4;j++){
                y=operate(x,a[3],op[j]);
                for(int k=1;k<=4;k++){
                    z=operate(y,a[4],op[k]);
                    if(z==24){
                        //sprintf转化输出内容到char[]
                        sprintf(str,"(((%d%c%d)%c%d)%c%d)",a[1],op[i],a[2],op[j],a[3],op[k],a[4]);
                        s[++cnt]=str;
                    }
                    yy=operate(a[3],a[4],op[k]);
                    zz=operate(xx,yy,op[j]);
                    if(zz==24){
                        sprintf(str,"((%d%c%d)%c(%d%c%d))",a[1],op[i],a[2],op[j],a[3],op[k],a[4]);
                        s[++cnt]=str;
                    }
                }
            }
        }
    }while(next_permutation(a+1,a+5));//全排列小技巧
    sort(s+1,s+1+cnt);
    printf("%s",s[1].c_str());//string转char[]
    return 0;
}