官方题解｜24点

抽屉原理

许多同学尝试通过模拟的方法来解决这道题，然而在模拟实现的过程中，一个明显的问题浮现出来：一旦出现错误，检查和调试都极为困难。那么，我们能否通过深入观察题目的性质，来降低模拟的复杂程度呢？

首先，让我们思考这样一个问题：给定任意两个数，我们是否能够通过一定的运算构造出一个 3 的倍数呢？

假设这两个数为 $a$ 和 $b$ 。如果其中一个数本身就是 3 的倍数，那么将这两个数相乘即可得到 3 的倍数，这种情况较为简单，我们暂不深入讨论。接下来考虑两个数都不是 3 的倍数的情况，此时它们除以 3 的余数（即模 3 的结果）共有 4 种组合：$\{1, 1\}$、$\{1, 2\}$、$\{2, 1\}$、$\{2, 2\}$。经过分析不难发现，对于这四种组合，我们都可以通过加法或者减法运算，使它们得到的结果成为 3 的倍数。由此，我们证明了任意两个数都能够通过适当的运算得到 3 的倍数。

已知 $24 \div 3 = 8$，此时问题就转化为：给定 4 个数，我们能否从中选取两个数，通过运算构造出 8 的倍数呢？为了简化问题，我们先排除这 4 个数中本身就包含 8 的倍数的情况。那么，当这 4 个数分别除以 8 取余数（即模 8 ）后，结果只会是 1、2、3、4、5、6、7 这 7 种情况。接下来我们思考，这 7 种余数情况中，哪些组合可以构成 8 的倍数呢？

通过计算可知，$1 + 7 = 8$，$3 + 5 = 8$，$2 \times 4 = 8$，$2 + 6 = 8$，$4 \times 6 = 24$（24 也是 8 的倍数）。基于这些组合，我们可以将这 7 种余数情况划分成 3 个集合：$\{1, 7\}$，$\{3, 5\}$，$\{2, 4, 6\}$。在这三个集合中，任意选取集合内的两个数，都可以通过相应的运算构成 8 的倍数。

由于我们一共有 4 个数，根据抽屉原理，这 4 个数中必然会有至少两个数的余数属于同一个集合。所以，我们可以先从这 4 个数中选取 2 个数，构造出 8 的倍数，再通过前面证明的方法构造出 3 的倍数，最后将得到的 8 的倍数和 3 的倍数相乘，就可以得到满足条件的结果。

综上所述，该算法的时间复杂度为 $O(T)$。

#include<bits/stdc++.h>
using namespace std;

string get(int a, int b, int x) {
    if ((a + b) % x == 0) {
        return "(" + to_string(a) + "+" + to_string(b) + ")";
    }
    if ((a - b) % x == 0) {
        return "(" + to_string(a) + "-" + to_string(b) + ")";
    } {
        return "(" + to_string(a) + "*" + to_string(b) + ")";
    }
};

string get(queue<int> &q, int x) {
    int a = q.front();
    q.pop();
    int b = q.front();
    q.pop();
    if ((a + b) % x == 0) {
        return "(" + to_string(a) + "+" + to_string(b) + ")";
    }
    if ((a - b) % x == 0) {
        return "(" + to_string(a) + "-" + to_string(b) + ")";
    } {
        return "(" + to_string(a) + "*" + to_string(b) + ")";
    }
};

void solve() {
    vector<int> a(4);
    string ans;
    for (auto &i: a) {
        cin >> i;
    }
    queue<int> q1, q2, q3, q4, q5;
    for (auto i: a) {
        if (i % 8 == 0)q1.emplace(i);
        else if (i % 8 == 1 || i % 8 == 7) {
            q2.emplace(i);
        } else if (i % 8 == 2 || i % 8 == 4 || i % 8 == 6) {
            q3.emplace(i);
        } else
            q4.emplace(i);
    }
    if (!q1.empty()) {
        ans = to_string(q1.front());
        q1.pop();
    } else if (q2.size() >= 2) {
        ans = get(q2, 8);
    } else if (q3.size() >= 2) {
        ans = get(q3, 8);
    } else {
        ans = get(q4, 8);
    }
    while (!q1.empty()) {
        q5.emplace(q1.front());
        q1.pop();
    }
    while (!q2.empty()) {
        q5.emplace(q2.front());
        q2.pop();
    }
    while (!q3.empty()) {
        q5.emplace(q3.front());
        q3.pop();
    }
    while (!q4.empty()) {
        q5.emplace(q4.front());
        q4.pop();
    }
    ans = ans + "*" + get(q5, 3);
    while (!q5.empty()) {
        ans = ans + "*" + to_string(q5.front());
        q5.pop();
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}