hdu1427.MD

日期 2021 / 11 / 4

题目

[题目链接]https://acm.dingbacode.com/showproblem.php?pid=1427

速算24点

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

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

解题思路

这个题目是一个dfs题，题目要求是给你四个数问你能不能通过加减乘除括号等操作使其计算结果为24，加减乘除的话就简单的dfs就行了，但是这里有个括号的选择，那我们就需要 考虑操作数之间的关系，首先除数不能为0以及商不能有余数，如果某一个数和下个数之间有括号隔开那么此时的sum值不算，sum的值直到括号里面的数都算完为止才进行计算，当然 对于一副扑克牌我们还需要进行对花色进行的赋值操作.

代码演示

#include <bits/stdc++.h>

#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 0, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e6 + 10;
using namespace std;

string s;
bool flag = false;
int a[10];

int get_sum(string s) {
  if (s[0] >= '2' && s[0] <= '9') {
    return s[0] - '0';
  }
  if (s == "10") {
    return 10;
  }
  switch (s[0]) {
    case 'A':
      return 1;
    case 'J':
      return 11;
    case 'Q':
      return 12;
    case 'K':
      return 13;
    default:
      return 0;
  }
}

void solve(int sum, int x, int index1) {  // 当前的值  下一个操作数的值  下一个操作数的索引
  if (index1 == 4) { // 到最后一个操作数
    if (sum + x == 24 || sum - x == 24 || sum * x == 24) {
      flag = true;
    }
    if (x != 0 && sum % x == 0 && sum / x == 24) {
      flag = true;
    }
    return;
  }
  solve(sum + x, a[index1 + 1], index1 + 1); // 当前的值和下一个操作数在同一括号内
  solve(sum - x, a[index1 + 1], index1 + 1);
  solve(sum * x, a[index1 + 1], index1 + 1);
  if (x != 0 && sum % x == 0) {
    solve(sum / x, a[index1 + 1], index1 + 1);
  }
  solve(sum, x + a[index1 + 1], index1 + 1); // 当前值和下个操作数不在一个括号内
  solve(sum, x - a[index1 + 1], index1 + 1);
  solve(sum, x * a[index1 + 1], index1 + 1);
  if (a[index1 + 1] != 0 && x % a[index1 + 1] == 0) {
    solve(sum, x / a[index1 + 1], index1 + 1);
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  while (cin >> s) {
    flag = false;
    a[1] = get_sum(s);
    for (int i = 2; i <= 4; i++) {
      cin >> s;
      a[i] = get_sum(s);
    }
    sort(a + 1, a + 5);
    do {
      solve(a[1], a[2], 2);
    } while (!flag && next_permutation(a + 1, a + 5));
    if (flag) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
  return 0;
}