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

Colubrid_L · 2026-01-26 15:33:21 · 题解

废话时间

萌新做过的第三道交互题。

正文

Part 1 怎么做交互题？

出门左转。

Part 2 怎么做这道题？

我的老师告诉我，拿到一道难题，当你不知所措时，可以先选择性的忽略掉一些条件。本题中，我们直接忽略“可能存在谎话”这一条件。如此一来，我们直接输出：

1 0 0
0 1 0
0 0 1

肥肠简单，那么按此思路，剩下两个询问应当被用来验证。

我们首先规定，第一个询问的回答为 a_1，第二个为 a_2，并以此类推。

若构造两个方程用于验证，则必须保证这两个方程存在本质上的不同，否则无法判断正误。本题解中，这两个方程为 a_1+a_2+a_3=a_4 与 a_1+2a_2+3a_3=a_5。这是两个本质不同的方程，可以用于验证。

Part 3 怎么验证方程的解？

因为只有一个方程错误，我们可以分类讨论。

• 若 a_4 是错误的，则必然存在 a_5 正确。验证 a_1+a_2+a_3 是否等于 a_5 即可。
• 若 a_5 是错误的，仿照上例，判断 a_4 即可。
• 若 a_1 是错误的，则必然存在 a_4、a_5 正确，此时令 t=a_4-a_2-a_3，则有 t+2a_2+3a_3=a_5。

这样就验证好了。反正验出来 a_1、a_2、a_3 中哪个错了，就把正确的填上去再输出。

代码

自认马蜂良好。

//written by Colubrid_L
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,temp;
signed main(){
    cout<<"1 0 0"<<endl,cin>>a;
    cout<<"0 1 0"<<endl,cin>>b;
    cout<<"0 0 1"<<endl,cin>>c;
    cout<<"1 1 1"<<endl,cin>>d;
    cout<<"1 2 3"<<endl,cin>>e;
    if(a+b+c==d){
        cout<<a<<" "<<b<<" "<<c<<'\n';
        return 0;
    }
    if(a+b*2+c*3==e){
        cout<<a<<" "<<b<<" "<<c<<'\n';
        return 0;
    }
    temp=d-a-b;
    if(a+b*2+temp*3==e){
        cout<<a<<" "<<b<<" "<<temp<<'\n';
        return 0;
    }
    temp=d-a-c;
    if(a+temp*2+c*3==e){
        cout<<a<<" "<<temp<<" "<<c<<'\n';
        return 0;
    }
    temp=d-b-c;
    if(temp+b*2+c*3==e){
        cout<<temp<<" "<<b<<" "<<c<<'\n';
        return 0;
    }
    return 0;
}

感谢阅读。