1 条题解
-
0
题目描述 有三个兄弟,编号分别为 (大哥)、(二哥)、(三弟)。 他们约定见面。到了时间,恰好有 两位兄弟准时到达,而 另一位兄弟迟到了。
输入给出准时到达的两位兄弟的编号 和 (,,顺序任意)。 你需要输出 迟到的那位兄弟的编号。
输入格式 一行,两个整数 和 ,用空格分隔。
输出格式 一个整数,即迟到兄弟的编号。
样例 输入
输出
解释:准时到达的是 号和 号,那么迟到的一定是 号。
解题思路 方法一:枚举所有可能情况 三个兄弟编号为 。 已知两个准时到达的编号 和 ,那么迟到的那个人就是 中 除了 和 之外 的那个数。
可以直接用 if-else 判断:
如果 或 ,则迟到的是 。
如果 或 ,则迟到的是 。
如果 或 ,则迟到的是 。
这种方法正确,但代码较长。
方法二:数学公式法(标程所用) 观察三个数 的和:
已知其中两个数 和 ,那么第三个数 一定满足:
因此: 这个公式无需任何条件判断,直接计算即可得到迟到的兄弟编号。
算法步骤 读入两个整数 和 。
计算 。
输出 。
正确性证明 因为 和 是 中两个不同的数,所以 的可能值为:
,此时 。
,此时 。
,此时 。
每种情况得到的 恰好是剩下的那个数,且 , 且 。
因此公式总是正确。
复杂度分析 时间复杂度:,只进行常数次算术运算。
空间复杂度:,只使用了几个整型变量。
如果兄弟编号不是 ,而是任意三个互不相同的整数 ,那么迟到者的编号可以用 计算。
本题也可以使用异或运算:,迟到的编号 = ?需要小心,异或用于三个不同的数时,,所以 ?验证:,,,确实成立。因此也可以用 cout << (a ^ b) << endl;。但标程采用加法,更直观。
本题非常简单,核心是观察到三个数的和为 ,从而用减法直接得出缺失的数。
这种“已知总和与部分元素,求另一元素”的技巧在竞赛中很常见。
- 1
信息
- ID
- 6269
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者