24点（暴力排列）

排列）"/>

24点（暴力排列）

2110: 24点
时间限制: 1 Sec 内存限制: 128 MB
提交: 149 解决: 21
[提交] [状态] [讨论版] [命题人:admin]
题目描述

yzj最近又迷上了一款游戏，名为《24点》，游戏规则很简单，给你4个数字，问你能否构成合法的表达式，使得这个表达式的计算结果正好为24。
注：
1.每个数字必须用且只能用一次;
2.表达式中的数字顺序可以不同于输入顺序;
3.运算符只有加减乘除且只能在两个数字之间（第一个数字之前和最后一个数字之后不能有运算符），优先级同c语言;
4.表达式可以添加任意多对括号，合法性同c语言;
5.如果要进行除法，请保证分母不为0且整除;
6.不能在数字前面添加负号使得数字变成负数进行运算，如给你1 2 3 4,形如1+(-2)+3+4的表达式是非法的，但是形如1-2+3+4的表达式是合法的。

输入

一行4个整数a1,a2,a3,a4， 1 <= a1,a2,a3,a4 <= 120

输出

如果能，输出Yes
如果不能，输出No

样例输入

【输入样例1】
4 4 1 2
【输入样例2】
17 14 43 45

样例输出

【输出样例1】
Yes
【输出样例2】
Yes

按题意模拟即可
用next_permutation()枚举数字的所有排列情况
对于某种排列，用四进制枚举出运算符的所有情况
最后再枚举括号的情况

注意
1.判断除法是否为整除（这个之前没看到一直wa），分母为0的情况
2.括号种类以及去除重复
3.next_permutation 的使用需要先sort 再用do while

非整除需要将所有转为double类型，判断时精度处理（本题不用）

具体看代码

#include <string>
#include <string.h>
#include <iostream>
#include <queue>
#include <math.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define LL long long
const int maxn = 1e5 + 55;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
int a[5];
int num[5];
int fnum[5];
int flag = 0;
int ff;int cal(int a,int b,int o)
{switch(o){case 1: return(a+b);case 2: return(a-b);case 3: return(a*b);}if(b==0){ff=1;return 999999;}else{if(a%b!=0){ff=1;return 99999;}else return a/b;}
}
void eq(int ans)
{if(ans-24==0){flag=1;}
}
void  doit(int o1,int o2,int o3)
{int x,y,z;ff=0;x=cal(a[1],a[2],o1);//((a 。b)。c)。dy=cal(x,a[3],o2);z=cal(y,a[4],o3);if(!ff) eq(z);ff=0;x=cal(a[2],a[3],o2);//(a。(b。c))。dy=cal(a[1],x,o1);z=cal(y,a[4],o3);if(!ff) eq(z);ff=0;x=cal(a[1],a[2],o1);//(a 。b)。(c。 d)y=cal(a[3],a[4],o3);z=cal(x,y,o2);if(!ff) eq(z);ff=0;x=cal(a[2],a[3],o2);// a。((b。c)。d )y=cal(x,a[4],o3);z=cal(a[1],y,o1);if(!ff) eq(z);ff=0;x=cal(a[3],a[4],o3);// a。(b。(c。d))y=cal(a[2],x,o2);z=cal(a[1],y,o1);if(!ff) eq(z);
}int main()
{flag = 0;a[1] = 1, a[2] = 2, a[3] = 3;//+ - * /for ( int i = 1; i <= 4; i++ ) scanf ( "%d", &fnum[i] );sort ( fnum + 1, fnum + 5 );do{for ( int i = 1; i <= 4; i++ ){for ( int j = 1; j <= 4; j++ ){for ( int k = 1; k <= 4; k++ ){for ( int o = 1; o <= 4; o++ ) a[o] = 1.0 * fnum[o];doit ( i, j, k );}}}}while ( next_permutation ( fnum + 1, fnum + 5 ) );if ( flag ){printf ( "Yes\n" );}else printf ( "No\n" );return 0;
}