LOJ

UOJ

分析

首先可以通过二分用两次询问把第一个字符问出来，假设是 $\texttt{A}$，那么接下来不会再出现 $\texttt{A}$。

考虑依次确定接下来的字符。有一个显然的 $2$ 次询问的方法，但是实际上可以 $1$ 次询问：设之前的串为 $\texttt{S}$，询问 $\texttt{SBSXBSXXSXY}$，那么如果返回值为 $|S|$ 则这一位为 $\texttt{Y}$、返回值为 $|S|+1$ 则这一位为 $\texttt{B}$、否则这一位为 $\texttt{X}$。

设当前在确定第 $i$ 位，这个串长为 $4(i-1)+7=4i+3$，当 $i=n$ 时并不合法。但是对于 $[1,n)$ 位我们只询问了 $2+(n-2)$ 次，所以只需要分别询问 $\texttt{SB}$ 和 $\texttt{SX}$ 即可确定最后一位。

这样子总共询问了 $n$ 次，可以通过此题。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#include "combo.h"
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

string guess_sequence(int n) {
    char ban;
    if (press("AB")) {
        if (press("A")) ban='A';
        else ban='B';
    } else {
        if (press("X")) ban='X';
        else ban='Y';
    }
    string res; res+=ban;
    char c[3]; int s=0;
    if (ban!='A') c[s++]='A';
    if (ban!='B') c[s++]='B';
    if (ban!='X') c[s++]='X';
    if (ban!='Y') c[s++]='Y';
    for (int i=1;i<n-1;++i) {
        string q=res+c[0]+res+c[1]+c[0]+res+c[1]+c[1]+res+c[1]+c[2];
        int l=press(q);
        res+=(l==i?c[2]:(l==i+1?c[0]:c[1]));
    }
    if (n>1) {
        if (press(res+c[0])==n) res+=c[0];
        else if (press(res+c[1])==n) res+=c[1];
        else res+=c[2];
    }
    return res;
}