题解：P13612 [IOI 2018] combo 组合动作

· · 题解

处处都很一眼的题，这居然是 IOI T1 吗 /xia

对每个测试用例，你调用该函数的次数不能超过 8000 次。

启示我们写出 4N 的解法。

显然每一位的确定都可以在 4 次内解决，从前往后确定即可。

诶等等看错题了，限制不是这个。

如果 q\le N+2，你的得分为 95。

我们需要更加优秀的做法。

你可以依次按最多 4N 个按键来完成一个组合动作。

启示我们把 4N 个询问压在一起。

接下来就可以充分发扬人类智慧了。

先去吃个饭。

吃完了也想出来了。

其实也不需要什么高妙的构造，乱糊就可以了。

我们的核心目的是这一位在三个不同的情况下对于我的构造都有不同的返回。

假设剩余的三种字符分别是 \texttt{A,B,C}。

那么我们在询问后面分别接上 \texttt{AA,AB,AC}，这样就可以以一种大力出奇迹的方式把 \texttt{A} 判出来。

那么还剩一个询问机会，剩下两个字符就随便做了。

不知道会不会假，实现一下。

喵的有坑，注意到最后一个询问可能会爆长度，拎出来刚好拿最后一次询问机会做掉就行了。

#include<bits/stdc++.h>
using namespace std;
int press(string p);
char A,B,C;
string check1(string s){
    int flc=press(s+'A'+s+'B')-s.size();
    if(flc){
        flc=press(s+'A')-s.size();
        if(flc)return s+'A';
        else return s+'B';
    }else{
        flc=press(s+'X')-s.size();
        if(flc)return s+'X';
        else return s+'Y';
    } 
}
string check2(string s){
    int flc=press(s+A+A+s+A+B+s+A+C+s+B)-s.size();
    if(flc==2)return s+A;
    if(flc==1)return s+B;
    if(flc==0)return s+C;
}
string guess_sequence(int N){
    string s=check1("");
    if(N==1)return s;
    if(s[0]=='A')A='B',B='X',C='Y';
    if(s[0]=='B')A='A',B='X',C='Y';
    if(s[0]=='X')A='A',B='B',C='Y';
    if(s[0]=='Y')A='A',B='B',C='X';
    for(int i=2;i<N;i++)s=check2(s);
    s=check1(s);
    return s;
}
// 「呃，我们连彼此的名字都不晓得，说这种话或许怪怪的。」
// 「但愿你能忘了我。」
// 少女交代完奇妙的话，就滴滴答答地向四处淌着水珠跑掉了。

// Tiat Siba Ignareo

很不符合我对 IOI 的想象。