【MX-J2-T0】Turtle and Equations

形式化题目

给定四个正整数 $a, b, c, d$ ，判断是否存在运算符 $op_1, op_2 \in \{+, -, \times\}$ （可重复），使得

(a \ op_1 \ b) \ op_2 \ c = d

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 15:01
 * update_at: 2026-08-14 15:05
 */
// brute.cpp：小数据暴力解，两重循环枚举两个方框的全部 3*3=9 种运算符组合，
// 与题意一一对应，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;

// 计算 x op y。
int calc(int x, int y, char op) {
    if (op == '+') return x + y;
    if (op == '-') return x - y;
    return x * y;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b >> c >> d;

    char ops[3] = {'+', '-', '*'};
    bool ok = false;
    for (int i = 0; i < 3 && !ok; i++) {        // 第一个方框
        for (int j = 0; j < 3 && !ok; j++) {    // 第二个方框
            int mid = calc(a, b, ops[i]);       // 先算括号内 a op1 b
            if (calc(mid, c, ops[j]) == d) ok = true;
        }
    }

    cout << (ok ? "Yes" : "No") << '\n';
    return 0;
}

brute.cpp 两层循环枚举第一个方框和第二个方框的各 3 种运算符，内层计算 $(a\ op_1\ b)\ op_2\ c$ 并与 $d$ 比较，逻辑与题意一一对应。枚举量只有 $3 \times 3 = 9$ 种组合，常数时间，暴力本身就是最终解法，不需要任何优化——这是本题的关键认识。

main.cpp 采用 rbook 模板 enumerate-dynamic-loop（递归实现 n 层循环，每层从 $[0, m)$ 中选择一个值）的结构：dfs(dep) 枚举第 dep 个方框的运算符，choose[dep] 记录选择，填满两个方框后在叶子检查等式。它枚举的集合与两重循环完全相同，只是把"两层循环"抽象成通用的"每层一个选择"的递归形态。

下面这张表展示样例 2（ $5, 2, 9, 27$ ）中 9 种组合的计算过程：

$op_1$	$op_2$	$(a\ op_1\ b)$	$(\dots)\ op_2\ c$	等于 27？
+	+	7	16	否
+	-	7	-2	否
+	$\times$	7	63	否
-	+	3	12	否
-	-	3	-6	否
-	$\times$	3	27	是
$\times$	+	10	19	否
$\times$	-	10	1	否
$\times$	$\times$	10	90	否

观察要点：九种组合中恰好 $(5 - 2) \times 9 = 27$ 命中。表中可见即使前八个组合都失败，最后一个也未必是解，必须全部枚举完才敢说 No；而一旦命中就可以提前输出 Yes。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 15:01
 * update_at: 2026-08-14 15:05
 */
// P10839 【MX-J2-T0】Turtle and Equations
// 枚举两个方框的运算符，共有 3*3=9 种组合。
// 本解对应 rbook 模板 enumerate-dynamic-loop：
// 递归实现 n 层循环，每层从 [0, m) 中选择一个值，这里是 2 层、每层 3 种运算符。
#include <bits/stdc++.h>
using namespace std;

int a, b, c, d;
char ops[3] = {'+', '-', '*'}; // 三种可用运算符
int choose[2];                 // choose[i]：第 i 个方框选中的运算符下标

// 计算 x op y。
int calc(int x, int y, char op) {
    if (op == '+') return x + y;
    if (op == '-') return x - y;
    return x * y;
}

// 递归枚举第 dep 个方框的运算符；填满两个方框后检查 (a op1 b) op2 c == d。
bool dfs(int dep) {
    if (dep == 2) {
        int mid = calc(a, b, ops[choose[0]]); // 先算括号内 a op1 b
        return calc(mid, c, ops[choose[1]]) == d;
    }
    for (int i = 0; i < 3; i++) {
        choose[dep] = i;
        if (dfs(dep + 1)) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b >> c >> d;
    cout << (dfs(0) ? "Yes" : "No") << '\n';

    return 0;
}

复杂度

时间：枚举 $3 \times 3 = 9$ 种组合， $O(1)$ 。
空间：常数个变量， $O(1)$ 。

总结

这道题的核心是枚举范围极小：两个位置各 3 种选择，总方案数 $3^2 = 9$ ，直接枚举即是正解。当"每层选择个数 × 层数"很小、且运算顺序固定时，暴力枚举不需要优化；rbook 模板 enumerate-dynamic-loop 把这种"n 层循环、每层 m 个选择"的枚举抽象成递归结构，choose[dep] 记录每层选择、叶子统一检查，适合推广到层数不固定的场景。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17题意：填两个运算符 op1, op2 ∈ {+, -, ×}
      (a op1 b) op2 c == d ?
        |
        v
枚举规模：3 × 3 = 9 种组合，常数
        |
        v
brute.cpp：两层 for 枚举所有组合
        |
        v
main.cpp：enumerate-dynamic-loop 递归枚举
   dfs(dep) 选第 dep 个方框的运算符
   choose[dep] 记录选择，叶子检查等式
        |
        v
存在命中 → Yes，否则 → No
复杂度 O(1)，空间 O(1)

图中主线是"枚举量极小 → 暴力即正解 → 递归与循环两种写法枚举同一集合"。这道题真正要掌握的不是优化，而是识别"组合数很小的枚举问题"并选择一种清晰的枚举写法。