题目详细分析

题目理解

题目描述了一个非常生活化的场景：

• 台湾有 5 家自助餐店，编号分别是 1、2、3、4、5
• 你从周一到周五，每天去一家不同的店买便当
• 周一到周四已经去了 4 家不同的店（输入给出）
• 周五要去 最后一家还没去过的店

换句话说：在 1 到 5 这五个数字中，输入给了四个互不相同的数字，你需要找出 缺少的那一个数字。

---

输入输出格式

输入：

• 一行包含四个整数 $a, b, c, d$，按顺序表示周一到周四去的餐厅编号
• 数据范围：$1 \le a, b, c, d \le 5$
• 保证四个数互不相同

输出：

• 一个整数，表示周五应该去的餐厅编号（即 1~5 中唯一没出现的那个）

---

解题思路详解

思路一：求和法

因为五个数字是 1, 2, 3, 4, 5，它们的和是固定的：

$$1 + 2 + 3 + 4 + 5 = 15$$

输入给了四个不同的数字，它们的和记为 $S = a + b + c + d$。

那么缺失的那个数字就是：

$$\text{答案} = 15 - S$$

为什么这样是对的？

设五个数字为 $\{1,2,3,4,5\}$，它们互不相同。如果拿走其中一个数 $x$，剩下四个数的和就是 $15 - x$。因此 $x = 15 - (\text{剩下四个数的和})$。

举例：

• 输入 1 3 2 5，$S = 1+3+2+5 = 11$，$15 - 11 = 4$ ✓
• 输入 2 5 4 3，$S = 2+5+4+3 = 14$，$15 - 14 = 1$ ✓

---

思路二：集合/标记法

用数组或集合记录哪些数字出现过：

1. 创建一个大小为 6 的布尔数组 visited（下标 1~5 使用）
2. 将输入的四个数标记为 true
3. 遍历 1 到 5，输出第一个未被标记的数

优点： 即使数字不是连续的 1~5，这种方法也适用（虽然本题不需要）。

举例：

• 输入 1 3 2 5
  • 标记：visited[1]=true, visited[3]=true, visited[2]=true, visited[5]=true
  • 遍历：1✓, 2✓, 3✓, 4✗ → 输出 4

---

思路三：异或法

异或运算有一个重要性质：

• $x \oplus x = 0$
• $x \oplus 0 = x$
• 异或满足交换律和结合律

计算 $1 \oplus 2 \oplus 3 \oplus 4 \oplus 5$ 的结果：

我们可以两两计算：

• $1 \oplus 2 = 3$
• $3 \oplus 3 = 0$
• $0 \oplus 4 = 4$
• $4 \oplus 5 = 1$

所以 $1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 = 1$

设缺失的数字为 $x$，那么输入的四位数异或结果应该等于：

$$(1 \oplus 2 \oplus 3 \oplus 4 \oplus 5) \oplus x = 1 \oplus x $$

但更直接的方法：

因为 $1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 = 1$，且异或满足结合律，所以：

$$a \oplus b \oplus c \oplus d \oplus x = 1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 = 1 $$

因此：

$$x = 1 \oplus a \oplus b \oplus c \oplus d$$

为什么这样是对的？

因为 $1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 = 1$，而 $a,b,c,d,x$ 正好是这五个数的一个排列，所以它们的异或也等于 1。从而可以解出 $x$。

举例：

• 输入 1 3 2 5
  • $1 \oplus 1 = 0$
  • $0 \oplus 3 = 3$
  • $3 \oplus 2 = 1$
  • $1 \oplus 5 = 4$
  • 输出 4 ✓

---

三种方法对比

方法	优点	缺点
求和法	最简单，一行代码	仅适用于连续整数
标记法	通用性强，思路清晰	代码稍长
异或法	位运算巧妙，空间 O(1)	需要理解异或性质

对于本题，求和法是最优选择，因为数字范围固定且连续。

---

完整 C++ 代码（详细注释版）

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

int main() {
    // 读取四个整数，表示周一到周四去的餐厅编号
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    
    // 方法一：求和法
    // 1+2+3+4+5 = 15
    int sum = a + b + c + d;
    int ans = 15 - sum;
    
    // 输出结果
    cout << ans << endl;
    
    return 0;
}

其他写法

// 方法二：标记法
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    
    bool visited[6] = {false};  // visited[0] 不使用
    visited[a] = true;
    visited[b] = true;
    visited[c] = true;
    visited[d] = true;
    
    for (int i = 1; i <= 5; i++) {
        if (!visited[i]) {
            cout << i << endl;
            break;
        }
    }
    
    return 0;
}

// 方法三：异或法
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    
    // 1 ^ 2 ^ 3 ^ 4 ^ 5 = 1
    int ans = 1 ^ a ^ b ^ c ^ d;
    cout << ans << endl;
    
    return 0;
}

---

测试用例验证

输入	1+2+3+4+5=15	输入和	15-和	输出
1 2 3 4	15	10	5
1 2 3 5		11	4
1 2 4 5		12	3
1 3 4 5		13	2
2 3 4 5		14	1
1 3 2 5		11	4
2 5 4 3		14	1

所有测试均通过。

---

总结

这是一道 Codeforces 入门级题目（通常难度 800）。核心知识点：

1. 固定集合 $\{1,2,3,4,5\}$ 的和为 15
2. 利用总和减去已知四个数的和得到缺失数
3. 注意输入保证四个数互不相同，无需额外校验

代码实现只需要 3 行核心代码，非常简洁。