P4692 添加运算符（【基础】）

解题思路

四个数之间有 3 个空位，每个空位可以填 +、-、*、/ 四种运算符，所以一共有 4×4×4=64 种填法。我们把所有填法都枚举一遍，每次从左往右计算整个式子的值，如果结果等于给定的 n，就把方法数加一。下面分四步实现。

**第一步，读入。**读入 4 个数存进 nums 数组，再读入目标值 target。

第二步，写运算函数。calc(x, y, op) 负责两个数做一次运算：op=0 是加法、1 是减法、2 是乘法、3 是除法（整除）。

**第三步，三重循环枚举。**三个空位分别用 i、j、k 表示，每个从 0 到 3 枚举四种运算符，一共 4×4×4=64 种情况。每次严格从左往右套用：calc(calc(calc(nums[0], nums[1], i), nums[2], j), nums[3], k)，结果存进 result。

**第四步，统计答案。**如果 result 等于目标值 target，方法数 ways 加一。最后输出 ways。

题目特别说明：运算符严格从左往右计算，不考虑乘法优先级，所以不能像普通四则运算那样先算乘法。除法是整除，也就是整数除法，两个整数相除只保留商的整数部分，比如 7/2=3。

打个比方：就像把三个空格当成三个抽屉，每个抽屉里放一个符号，我们把所有可能的放法都试一遍，看哪种能让结果正好等于目标值。因为只有 64 种情况，非常少，全部试完也不会超时。

参考代码

// P4692 添加运算符：4个数之间填+ - * /，从左往右算，统计结果等于n的方案数
#include <iostream>
using namespace std;

// 两个数做一次运算，op=0加 1减 2乘 3整除
int calc(int x, int y, int op) {
    if (op == 0) return x + y;
    if (op == 1) return x - y;
    if (op == 2) return x * y;
    return x / y;   // 整除
}

int main() {
    int nums[4], target;
    for (int i = 0; i < 4; i++) cin >> nums[i];
    cin >> target;
    int ways = 0;
    // 枚举3个空位的4种运算符，共4*4*4=64种
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++) {
                // 严格从左往右计算：((a[0] op1 a[1]) op2 a[2]) op3 a[3]
                int result = calc(calc(calc(nums[0], nums[1], i), nums[2], j), nums[3], k);
                if (result == target) ways++;
            }
    cout << ways << endl;
    return 0;
}

复杂度分析

枚举 4×4×4=64 种情况，每次计算是常数次运算，时间复杂度 O(1)。空间上只用几个变量，也是 O(1)。