题解：P12295 [ICPC 2022/2023 WF] 斯芬克斯的谜语

Ian_NIE · 2025-06-01 11:22:37 · 题解

0x00 前言

这是一道简单的交互题。

另外：没有必要和洛谷的帮助中心一样写 extern "C"，直接先输出再输入即可，毕竟原题没有给出固定的交互库。

关于题目已经给出的一个 Python 代码是 Special Judge，并不是交互库。

0x01 题目大意

现在有三个未知数 a，b 和 c。现在你可以向评测提问五个式子，形如 x_1a + x_2b + x_3c，评测机会告诉你这个式子的结果。但是在五个回复中最多存在一个答案是错的，求 a，b，c。

0x02 算法设计（？）

准确来说是数学分析。

对于这个问题，我们可以先询问评测机 a，b，c。接下来我们需要一个检查这三个是否正确的式子，所以我们想到了 a + b + c。但是，我们不能够确定这个“试金石”是否正确，所以我们还需要一块完全不一样的：a + 2b + 3c。

注意，我们不可以把两块试金石造成 a + b + c 和 2a + 2b + 2c 这样的格式，否则如果这两个都是正确的，我们就无法分辨 a，b，c 中错误的是哪一个了。所以，我们的“double check”必须和原来的那个不等价但是此时，我们的试金过程也变得复杂。

首先，我们先假设评测机回答的是这样五个式子：

继续，如果 A + B + C = D 或者 A + 2B + 3C = E，那么对应的四个式子一定是对的。因为如果有错的，那么那个错的结果和评测机给出的结果的两个式子全部都是错的，矛盾，所以都是对的。此时显然：

如果上面的两个全部都是错的，那么证明 D 和 E 全部都是对的，因为如果有一个是错的，那么另一个和 A，B，C 就都是对的，上面的式子就有一个会成立，矛盾，所以都是对的。现在我们继续检查 A，B，C 当中谁是错的。

假设 A 是错的，那么 E - D = B + 2C，因为剩下的都是对的。反过来，如果这个式子是对的，那么 A 就是错的。和上面证明的逻辑相同，这个式子代表了 B，C，D，E 全部都是对的，所以 A 就是错的（显然 A，B，C 中必须有一个是错的，所以 A 不可能是对的）。此时：

同理可得，当 E - 2D = -A + C 时，B 错，所以：

第三种情况读者自证不难。

所以，代码就是 if else，没有难度了吧。

0x03 部分代码实现

下面的求答案的过程大家自己写吧，很简单。我就简单说一下输入输出，直接这样写就可以。

大家都是第一次做交互题吧，经验大佬请直接跳过。

/*
a = ans1;
b = ans2;
c = ans3;
a + b + c = ans4;
a + 2b + 3c = ans5;
*/ 
    cout << "1 0 0" << endl, cin >> ans1;
    cout << "0 1 0" << endl, cin >> ans2;
    cout << "0 0 1" << endl, cin >> ans3;
    cout << "1 1 1" << endl, cin >> ans4;
    cout << "1 2 3" << endl, cin >> ans5;

0x04 完整代码

一个整合没有解释。

0x05 后记

本人第一次写交互题。

AC 记录。