P1834 题解

· · 题解

P1834 题解

前置知识

题目解法

最暴力的解法。

通过枚举半天，会发现答案的式子只有可能是以下几种（以下用问号代表运算符）：

  1. (((a?b)?c)?d)
  2. ((a?(b?c))?d)
  3. (a?(b?(c?d)))
  4. ((a?b)?(c?d))
  5. (a?((b?c)?d))

那我们可以先全排列枚举四个数字的方法，然后再枚举三个运算符，最后枚举这 5 种情况，如果等于 24 就把式子转成字符串，放到数组里。排序就可以得到字典序最小的。

容易发现循环只会有 24\times4^3=1536 次，根本不会超时。

代码有点混乱，但是相比其它大佬算短的，建议在清醒的时候写这道题。

AC 代码

#include<iostream>
#include<algorithm>
using namespace std;
int a[8],cnt; 
char op[8]={'+','-','*','/'};
int calc(int x,int y,int op){//计算用的函数
    if(op==0)return x+y;
    if(op==1)return x-y;
    if(op==2)return x*y;
    if(op==3&&y!=0&&x%y==0)return x/y;
    return -114;//如果除数为0或者不整除就返回一个奇怪的值
}
string ans[100005];
string str(int x){//把数字转成字符串
    string s="";
    s.push_back(x+'0');
    return s;
}
int main(){
    for(int i=1;i<=4;++i)cin>>a[i];
    for(int qwq=1;qwq<=24;++qwq){//枚举全排列
        for(int i=0;i<4;++i){
            for(int j=0;j<4;++j){
                for(int k=0;k<4;++k){//枚举三个运算符
                //以下为 5 种情况的判断
                    if(calc(calc(calc(a[1],a[2],i),a[3],j),a[4],k)==24){
                        ans[++cnt]="((("+str(a[1])+op[i]+str(a[2])+")"+op[j]+str(a[3])+")"+op[k]+str(a[4])+")";
                    }
                    if(calc(calc(a[1],calc(a[2],a[3],j),i),a[4],k)==24){
                        ans[++cnt]="(("+str(a[1])+op[i]+"("+str(a[2])+op[j]+str(a[3])+"))"+op[k]+str(a[4])+")";
                    }
                    if(calc(a[1],calc(a[2],calc(a[3],a[4],k),j),i)==24){
                        ans[++cnt]="("+str(a[1])+op[i]+"("+str(a[2])+op[j]+"("+str(a[3])+op[k]+str(a[4])+")))";
                    }
                    if(calc(calc(a[1],a[2],i),calc(a[3],a[4],k),j)==24){
                        ans[++cnt]="(("+str(a[1])+op[i]+str(a[2])+")"+op[j]+"("+str(a[3])+op[k]+str(a[4])+"))";
                    }
                    if(calc(a[1],calc(calc(a[2],a[3],j),a[4],k),i)==24){
                        ans[++cnt]="("+str(a[1])+op[i]+"(("+str(a[2])+op[j]+str(a[3])+")"+op[k]+str(a[4])+"))";
                    }
                }
            }
        }
        next_permutation(a+1,a+5);//STL 的函数，很好用
    }
    sort(ans+1,ans+cnt+1);//排序
    cout<<ans[1];//输出字典序最小的一个
    return 0;
}