经典爆搜--题解 P1236 【算24点】

· · 题解

此题无脑爆搜可做。因为：

全排列：4!

每次全排列枚举运算符：4^3

如果用我的判断两两先算再相运算的方法，还要加上4^3

所以最终复杂度是：

4!*(2*4^3)=3097

反正再怎么折腾也不会TLE。

首先第一步：忽略运算顺序，顺序计算配合全排列。

然后，你就可以再两两数之间枚举运算符，这里有一个奇技淫巧：

inline int plus(int x,int y){return x+y;}
inline int minus(int x,int y){return x>y?x-y:-1;}
inline int times(int x,int y){return x*y;}
inline int divi(int x,int y){return y!=0&&x%y==0&&x>y?x/y:-1;}
int (*oper[10])(int,int)={NULL,plus,minus,times,divi};
char oper_[10]={'\0','+','-','*','/'};

这样就可以简单的

for(int i=1;i<=4;i++)int result=oper[k](x,y)

了。自认为是简单很多的。

然后你就可以马上搞出一个60行的程序来：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>

int x[10],vis[10],r[10];

inline int plus(int x,int y){return x+y;}
inline int minus(int x,int y){return x>y?x-y:-1;}
inline int times(int x,int y){return x*y;}
inline int divi(int x,int y){return y!=0&&x%y==0&&x>y?x/y:-1;}
int (*oper[10])(int,int)={NULL,plus,minus,times,divi};
char oper_[10]={'\0','+','-','*','/'};

int op[10],left[10],right[10],re[10];
inline void print(){
    for(register int i=1;i<=3;i++){
        if(left[i]<right[i])std::swap(left[i],right[i]);
        std::printf("%d%c%d=%d\n",left[i],oper_[op[i]],right[i],re[i]);
    }
}
inline void calc(int i,int result){
    if(i==4)
      if(result==24){
        print();
        exit(0);
      }else return;
    for(register int j=1;j<=4;j++){
        int x=oper[j](result,r[i+1]);
        if(x>0){
            op[i]=j;
            left[i]=result;
            right[i]=r[i+1];
            re[i]=x;
            calc(i+1,x);
        }
    }
}

void DFs(int i){
    if(i==5){
        calc(1,r[1]);
        return;
    }
    for(register int j=1;j<=4;j++)
      if(!vis[j]){
        r[i]=x[j];
        vis[j]=true;
        DFs(i+1);
        vis[j]=false;
      }
}
int main(){
    for(register int i=1;i<=4;i++)std::cin>>x[i];
    DFs(1);
    std::puts("No answer!");
    return 0;
}

然后悲惨的WA一个点。这里展示一下，比如说你是

1 1 3 5

就会输出No answer!

然而正解是：

3+1=4
5+1=6
6*4=24

标注一下，这绝对不是真实数据

这是什么原因呢？很明显，你的运算只支持:

      result
     op
    re 5 
   op
  re 3
 op
1 1

的一棵严重左偏表达式树，而不支持：

   result
   op
  re re
 op   op
1 3   1 5

的形态。

如何解决？

我用的方法，因为计算函数是递归执行的，相对不灵活修改，又鉴于数据如此之小，我用了暴力的方法解决。

calc(1,0);//每次生成全排列后计算结果，递归
for(register int i=1;i<=4;i++)
    for(register int j=1;j<=4;j++){
         int x=oper[i](r[1],r[2]),y=oper[j](r[3],r[4]);
         if(x<=0||y<=0)continue;
         left[1]=r[1],right[1]=r[2],re[1]=x,op[1]=i;
         left[2]=r[3],right[2]=r[4],re[2]=y,op[2]=j;
         for(register int k=1;k<=4;k++)
            if(oper[k](x,y)==24){
             left[3]=x,right[3]=y,re[3]=oper[k](x,y),op[3]=k;
             print();
             exit(0);
             }
         }//丧心病狂了，特判两辆算出，再相运算的方法

然后就过了...

代码71行，算是比较短的了吧。这个解法并不优美，但是个人觉得用函数指针数组的方法进行四则运算是值得借鉴的方法。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>

int x[10],vis[10],r[10];

inline int plus(int x,int y){return x+y;}
inline int minus(int x,int y){return x>y?x-y:-1;}
inline int times(int x,int y){return x*y;}
inline int divi(int x,int y){return y!=0&&x%y==0&&x>y?x/y:-1;}
int (*oper[10])(int,int)={NULL,plus,minus,times,divi};
char oper_[10]={'\0','+','-','*','/'};

int op[10],left[10],right[10],re[10];
inline void print(){
    for(register int i=1;i<=3;i++){
        if(left[i]<right[i])std::swap(left[i],right[i]);
        std::printf("%d%c%d=%d\n",left[i],oper_[op[i]],right[i],re[i]);
    }
}
inline void calc(int i,int result){
    if(i==4)
      if(result==24){
        print();
        exit(0);
      }else return;
    for(register int j=1;j<=4;j++){
        int x=oper[j](result,r[i+1]);
        if(x>0){
            op[i]=j;
            left[i]=result;
            right[i]=r[i+1];
            re[i]=x;
            calc(i+1,x);
        }
    }
}

void DFs(int i){
    if(i==5){
        calc(1,r[1]);
        for(register int i=1;i<=4;i++)
          for(register int j=1;j<=4;j++){
            int x=oper[i](r[1],r[2]),y=oper[j](r[3],r[4]);
            if(x<=0||y<=0)continue;
            left[1]=r[1],right[1]=r[2],re[1]=x,op[1]=i;
            left[2]=r[3],right[2]=r[4],re[2]=y,op[2]=j;
            for(register int k=1;k<=4;k++)
              if(oper[k](x,y)==24){
                left[3]=x,right[3]=y,re[3]=oper[k](x,y),op[3]=k;
                print();
                exit(0);
              }
          }//丧心病狂了，特判两辆算出，再相运算的方法 
        return;
    }
    for(register int j=1;j<=4;j++)
      if(!vis[j]){
        r[i]=x[j];
        vis[j]=true;
        DFs(i+1);
        vis[j]=false;
      }
}
int main(){
    for(register int i=1;i<=4;i++)std::cin>>x[i];
    DFs(1);
    std::puts("No answer!");
    return 0;
}

此题还有一个坑：你想判减法，除法的小数，负数和0，但是不自觉的就写出return x%y==0?x/y:-1;来，这时如果y本身就是0，就直接RE了...因为&&,||是短路的（即,&&碰到错的后面就不知行,||碰到对的后面就不执行），可以在前面再判一下y!=0就可以了