首页 > 代码库 > HNU 12886 Cracking the Safe 二十四点的判断

HNU 12886 Cracking the Safe 二十四点的判断

经典的一个题,今天竟然写跪了……

题意:

    给你4个数字,让你判断是否能通过四则运算和括号,凑成24点。

思路:

    暴力枚举运算顺序和运算符。

代码:

   

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <time.h>15 16 using namespace std;17 18 const int INF = 1<<30;19 const double eps = 1e-6;20 21 double a[4];22 inline double myAbs(double x) {23     return x>0 ? x : -x;24 }25 26 bool dfs(double S[], int cnt) { //S[]中存放当前还有的数字27 //计算方法: 每次从剩下的数字里取出两个数运算,相当于枚举运算顺序28     if (cnt==1) //最后一个数字29         return myAbs(24-S[0])<eps;30 31     double b[4];32     for (int i = 0; i < cnt; i++) //枚举两个运算的数字33         for (int j = 0; j < cnt; j++) if (i!=j) {34             for (int k = 0, p = 1; k < cnt; k++) {35                 if (k!=i&&k!=j)36                     b[p++] = S[k];37             }38             //枚举运算39             b[0] = S[i]+S[j];40             if (dfs(b, cnt-1)) return true;41             b[0] = S[i]-S[j];42             if (dfs(b, cnt-1)) return true;43             b[0] = S[i]*S[j];44             if (dfs(b, cnt-1)) return true;45             b[0] = S[i]/S[j];46             if (dfs(b, cnt-1)) return true;47         }48     return false;49 }50 51 void solve() {52     do { //枚举排列53         if (dfs(a, 4)) {54             puts("YES");55             return ;56         }57     }while (next_permutation(a, a+4));58     puts("NO");59 }60 61 int main() {62     #ifdef Phantom0163         freopen("HNU12879.txt", "r", stdin);64     #endif //Phantom0165 66     int T;67     scanf("%d", &T);68     while (T--) {69         for (int i = 0; i < 4; i++)70             scanf("%lf", &a[i]);71         solve();72     }73 74     return 0;75 }
View Code