大家好，我是小码匠，今天继续划水，这道题真的不水，一开始没有考虑括号，样例过了，一提交就挂了。
后来看了看题解，学习了新思路。
前置知识
- 全排列
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成： 14道
- 待完成：286道
题目描述
题目地址：
- 洛谷：https://www.luogu.com.cn/problem/P9861
有一个算 24 点的游戏，每局游戏都会给你 4 个整数(1≤ 每个数 ≤13，表示你所需要用其来凑出 24 点。你可以将其中的两个数通过加减乘除的运算，得到一个新数，一直重复如此的操作，直到你剩下一个整数，那便是你游戏的答案。
现在，你需要根据给出的那 4 个整数，来计算出一个整数 n，使其最接近 24，同时也不能超出 24，问 n 是多少。
你一共玩了 N(1≤N≤5) 局这样的游戏，请你求出每局游戏对应的 n。
输入输出样例
输入 #1复制
代码语言：javascript复制3
3
3
3
3
1
1
1
1
12
5
13
1
输出 #1复制
代码语言：javascript复制24
4
21
题解
- https://www.luogu.com.cn/problem/solution/P9861
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int n, a[4];
bool is;
int answer(int x, int y, int t) {
if (t == 0) {
return x y;
}
if (t == 1) {
return x - y;
}
if (t == 2) {
return x * y;
}
if (t == 3 && y != 0 && x % y == 0) {
return x / y;
}
is = false;
return 0;
}
void best_coder() {
cin >> n;
while (n--) {
int ans = 0;
for (int i = 0; i < 4; i) {
cin >> a[i];
}
do {
for (int i = 0; i < 4; i) {
for (int j = 0; j < 4; j) {
for (int s = 0; s < 4; s) {
is = true;
int cnt = answer(answer(answer(a[0], a[1], i), a[2], j), a[3], s);
if (is && cnt <= 24) {
ans = max(ans, cnt);
}
is = true;
cnt = answer(answer(a[0], answer(a[1], a[2], j), i), a[3], s);
if (is && cnt <= 24) {
ans = max(ans, cnt);
}
is = true;
cnt = answer(a[0], answer(a[1], answer(a[2], a[3], s), j), i);
if (is && cnt <= 24) {
ans = max(ans, cnt);
}
is = true;
cnt = answer(answer(a[0], a[1], i), answer(a[2], a[3], s), j);
if (is && cnt <= 24) {
ans = max(ans, cnt);
}
is = true;
cnt = answer(a[0], answer(answer(a[1], a[2], j), a[3], s), i);
if (is && cnt <= 24) {
ans = max(ans, cnt);
}
}
}
}
} while (next_permutation(a, a 4));
cout << ans << 'n';
}
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
学习代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int ans;
int hand[4]; // The given card hand.
vector<int> hand_permutation; // The generated permutation of the card hand.
bool chosen[4]; // Whether a given card is present in `hand_permutation`.
// Function that takes in two numbers and an operation and returns the result.
int operation(int op, int num1, int num2) {
switch (op) {
case 0:
return num1 num2;
case 1:
return num1 - num2;
case 2:
return num1 * num2;
case 3: {
// The divisor cannot be 0 and the quotient must be a whole number.
if (num2 == 0 || num1 % num2 != 0) { return INT32_MIN; }
return num1 / num2;
}
}
return INT32_MIN;
}
// Function that generates all possible permutations of the card hand.
void generate_hand_permutation() {
if (hand_permutation.size() == 4) {
// We have generated a permutation, so we can try placing the
// operators.
for (int op1 = 0; op1 < 4; op1 ) {
for (int op2 = 0; op2 < 4; op2 ) {
for (int op3 = 0; op3 < 4; op3 ) {
int first = operation(op1, hand_permutation[0],
hand_permutation[1]);
// If the operation is invalid, continue;
if (first == INT32_MIN) { continue; }
int second = operation(op2, first, hand_permutation[2]);
if (second == INT32_MIN) { continue; }
int third = operation(op3, second, hand_permutation[3]);
if (third == INT32_MIN) { continue; }
if (third <= 24) { ans = max(ans, third); }
}
}
}
// Case 2: (( ) ( ))
for (int op1 = 0; op1 < 4; op1 ) {
for (int op2 = 0; op2 < 4; op2 ) {
for (int op3 = 0; op3 < 4; op3 ) {
int first = operation(op1, hand_permutation[0],
hand_permutation[1]);
if (first == INT32_MIN) { continue; }
int second = operation(op2, hand_permutation[2],
hand_permutation[3]);
if (second == INT32_MIN) { continue; }
int third = operation(op3, first, second);
if (third == INT32_MIN) { continue; }
if (third <= 24) { ans = max(ans, third); }
}
}
}
} else {
// Otherwise, we continue to build our permutation array.
for (int i = 0; i < 4; i ) {
if (chosen[i]) continue;
chosen[i] = true;
hand_permutation.push_back(hand[i]);
generate_hand_permutation();
chosen[i] = false;
hand_permutation.pop_back();
}
}
}
int main() {
int num_hands;
cin >> num_hands;
for (int h = 0; h < num_hands; h ) {
ans = INT32_MIN;
for (int i = 0; i < 4; i ) { cin >> hand[i]; }
// Start complete search.
generate_hand_permutation();
cout << ans << "n";
}
}
