***萌新6：24点（爆搜）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

题目描述

在扑克牌中有种玩法叫做24点，目标是用给定的四张牌通过基本的数学运算（加、减、乘、除）得到24。24点的玩法规则如下：

1. 准备一副扑克牌，去掉大小王，使用 `A,2,3,4,5,6,7,8,9,10,J,Q,K` 分别表示 `1,2,3,4,5,6,7,8,9,10,11,12,13`。每种各四张，共52张牌。
2. 每次从这些牌中任意取出四张牌。
3. 使用这四张牌的数字，通过加法、减法、乘法和除法运算，最终得到24。（除法是正常的数学除法，即有可能出现除不尽的情况，比如 1÷3=131\div 3=\dfrac131÷3=31​）
4. 每张牌只能使用一次，可以任意调换数字的顺序，可以使用任意的括号来改变运算顺序。
5. 玩家需要找到至少一种解决方案。如果无法用四张牌得到24点，则说明没有解。

现在需要你判断某种情况下是否有解。

输入描述:

第一行一个正整数 TTT (1≤T≤1000)(1\le T\le 1000)(1≤T≤1000)，表示数据的组数。

接下来 TTT 行，每行四个字符串，表示取出的四张牌的点数，输入的扑克牌点数只会出现 `A,2,3,4,5,6,7,8,9,10,J,Q,K`。

输出描述:

输出一行一个字符串，如果有解输出 `YES`，无解输出 `NO`

示例1

输入

复制5 8 2 2 A 5 J 10 4 9 K A A A 10 10 A 10 8 9 7

5
8 2 2 A
5 J 10 4
9 K A A
A 10 10 A
10 8 9 7

输出

复制YES YES YES NO YES

YES
YES
YES
NO
YES

做法

#include<bits/stdc++.h>
using namespace std;
int t;
unordered_map<string,int> mp;
const double eps=1e-9;
int merger(int id,int op,vector<double>&v){
    if(v.size()<=id+1) return 0;
    if(op==3&&v[id+1]==0) return 0;
    
    if(op==0) v[id]+=v[id+1];
    if(op==1) v[id]-=v[id+1];
    if(op==2) v[id]*=v[id+1];
    if(op==3) v[id]/=v[id+1];
    v.erase(v.begin()+id+1);
    return 1;
}
double compute(int id,int op,vector<int> &v){
    vector<double> a;
    for(int i=0;i<v.size();i++) a.push_back(v[i]);
    int idd,opp;
    idd=id%3,id/=3;
    opp=op%4,op/=4;
    if(!merger(idd,opp,a)) return -1;
    idd=id;
    opp=op%4,op/=4;
    if(!merger(idd,opp,a)) return -1;
    idd=0;
    opp=op%4,op/=4;
    if(!merger(idd,opp,a)) return -1;
    return a[0];
}
int check(vector<int> &v){
    sort(v.begin(),v.end());//得先排序！！！
    do{
        for(int i=0;i<=5;i++){//运算符
            for(int j=0;j<64;j++){//加减乘除四个运算符0，1，2，3
                if(abs(compute(i,j,v)-24)<=eps) return 1;
            }
        }
    }while(next_permutation(v.begin(),v.end()));
    return 0;
}
int main(){
    scanf("%d",&t);
    mp["A"]=1,mp["2"]=2,mp["3"]=3,mp["4"]=4,mp["5"]=5,mp["6"]=6;
    mp["7"]=7,mp["8"]=8,mp["9"]=9,mp["10"]=10,mp["J"]=11,mp["Q"]=12,mp["K"]=13;
    while(t--){
        string s;
        vector<int> v;
        for(int i=1;i<=4;i++){
            cin>>s;
            v.push_back(mp[s]);
        }
        if(check(v)) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}