2021-03-15

2024-01-29 19:32:46

HDU 1427

[题目链接]=(https://www.nitacm.com/problem_show.php?pid=1405)

速算24点相信绝大多数人都玩过。就是随机给你四张牌，包括A(1),2,3,4,5,6,7,8,9,10,J(11),Q(12),K(13)。要求只用’+’,’-’,’*’,’/'运算符以及括号改变运算顺序，使得最终运算结果为24(每个数必须且仅能用一次)。游戏很简单，但遇到无解的情况往往让人很郁闷。你的任务就是针对每一组随机产生的四张牌，判断是否有解。我们另外规定，整个计算过程中都不能出现小数。

Input

每组输入数据占一行，给定四张牌。

Output

每一组输入数据对应一行输出。如果有解则输出"Yes"，无解则输出"No"。

Sample Input

A 2 3 6
3 3 8 8

Sample Output

Yes
No

Code

#include<iostream>
#include<algorithm>
#include<string>
int num[5];
int flag;
using namespace std;
int change(string arg);//把输入转换成数学,输入10的情况比较特殊
void DFS(int sum,int temp,int cnt);//DFS函数啦
int main()
{
    string a,b,c,d;
    while(cin>>a>>b>>c>>d)
    {
        flag=0;
        num[1]=change(a);
        num[2]=change(b);
        num[3]=change(c);
        num[4]=change(d);
        sort(num+1,num+1+4);//首先要对num数组进行排序,默认从小到大


        do{
            DFS(num[1],num[2],2);   //之所以要用do while是因为要把刚排好序的num数组给DFS一次,如果直接用while数组,会越过这一种情况
        }while(next_permutation(num+1,num+1+4)&&!flag);

        if (flag)   cout<<"Yes\n";
        else cout<<"No\n";
    }

    return 0;
}
int change(string arg)
{
    if (arg[0]=='A') return 1;
    else if (arg[0]=='J') return 11;
    else if (arg[0]=='Q') return 12;
    else if (arg[0]=='K') return 13;
    else if (isdigit(arg[0])&&arg[1]=='\0')   return arg[0]-'0';//(isdigit(arg[0])&&!isdigit(arg[0]))也完全可以
    else    return 10;
}

void DFS(int sum,int temp,int cnt)
{
    if (flag)   return;//用flag标记是否已经找到答案
    if (cnt==4)//当cnt==4的时候进行判断
    {
        if (sum+temp==24||sum-temp==24||sum*temp==24) flag=1;
        if (temp!=0&&sum%temp==0&&sum/temp==24) flag=1;
        return;
    }
    DFS(sum+temp,num[cnt+1],cnt+1);
    DFS(sum-temp,num[cnt+1],cnt+1);
    DFS(sum*temp,num[cnt+1],cnt+1);
    if (temp!=0&&sum%temp==0)
        DFS(sum/temp,num[cnt+1],cnt+1);//先把前两个数结合,相当于加个括号,做除法的时候要判断一下分母是零的情况(虽然这里不会),并且还要可以整除,因为题目要求不能有小数

    DFS(sum,temp+num[cnt+1],cnt+1);
    DFS(sum,temp-num[cnt+1],cnt+1);
    DFS(sum,temp*num[cnt+1],cnt+1);
    if (num[cnt+1]!=0&&temp%num[cnt+1]==0)
        DFS(sum,temp/num[cnt+1],cnt+1); //先把中间两个数进行结合
}

详细的都在代码注释里面了,对于next_permutation(),不太清楚的,自己去百度一下,就是一个生成全排列的,用这个函数很方便,包含在头文件algorithm中

码农公寓