【第14题】题解及代码分享：这题不水吧，大模拟+全排列，[CCC 2008 S4] Twenty-four

3
3
3
3
3
1
1
1
1
12
5
13
1

24
4
21

#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;
}

#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";
	}
}