首页 > 其他分享 >hdu1427-速算24点

hdu1427-速算24点

时间:2023-02-06 14:03:39浏览次数:62  
标签:24 速算 hdu1427 dfs int num str ans


速算24点


Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4374    Accepted Submission(s): 1079


Problem Description


速算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


 



Author


LL


 



Source


​ACM暑期集训队练习赛(三)​




这个很容易就可以想到dfs的,但是怎么dfs是个问题

​点这里了解详情​


#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int flag;
int num[10];
void dfs(int x,int y,int ans){
if(flag) return ;
if(ans==3){
if(x+y==24||x-y==24||x*y==24) flag=1;
if(y!=0&&x%y==0&&x/y==24) flag=1;
return ;
}
dfs(x+y,num[ans+1],ans+1);
dfs(x-y,num[ans+1],ans+1);
dfs(x*y,num[ans+1],ans+1);
if(y!=0&&x%y==0)
dfs(x/y,num[ans+1],ans+1);
dfs(x,y+num[ans+1],ans+1);
dfs(x,y-num[ans+1],ans+1);
dfs(x,y*num[ans+1],ans+1);
if(num[ans+1]!=0&&y%num[ans+1]==0)
dfs(x,y/num[ans+1],ans+1);
}
int main()
{
char str[10];
while(gets(str)){
int len=strlen(str);
sort(str,str+len);
int k=0;
for(int i=0;i<len;i++){
if(str[i]=='A') num[k]=1;
else if(str[i]=='J') num[k]=11;
else if(str[i]=='Q') num[k]=12;
else if(str[i]=='K') num[k]=13;
else if(str[i]=='1') num[k]=10;
else if(str[i]=='0'||str[i]==' ') continue;
else num[k]=str[i]-'0';
k++;
}
sort(num,num+4);
flag=0;
do{
dfs(num[0],num[1],1);
}while(next_permutation(num,num+4)&&!flag);
if(flag) printf("Yes\n");
else printf("No\n");
}
return 0;
}




标签:24,速算,hdu1427,dfs,int,num,str,ans
From: https://blog.51cto.com/u_14235050/6039048

相关文章