你在玩一个动作游戏。游戏控制器有 $4$ 个按键，A、B、X 和 Y。在游戏中，你用组合动作来赚金币。你可以依次按这些按键来完成一个组合动作。
这个游戏有一个隐藏的按键序列，可以表示为由这 $4$ 个字符组成的串 $S$。你并不知道这个串 $S$，但是你知道它的长度为 $N$。
你还知道，$S$ 的首字符不会在串中重复出现。例如，$S$ 可以是 "ABXYY" 或者 "XYYAA"，但不能是 "AAAAA" 或 "BXYBX"。
你可以依次按最多 $4N$ 个按键来完成一个组合动作。串 $p$ 为你所按的按键序列。你用这个组合动作赚到的金币数量，等于同时为 $p$ 之子串和 $S$ 之前缀的最长字符串的长度。串 $t$ 的子串定义为 $t$ 中的连续字符序列 (可以为空)。$t$ 的前缀定义为 $t$ 的子串，其或者为空，或者包含 $t$ 的首字符。
例如，如果 $S$ 是 "ABXYY"，而 $p$ 是 "XXYYABYABXAY"，你会得到 $3$ 个金币，因为 "ABX" 是可作为 $p$ 的子串的 $S$ 的前缀中最长的。
你的任务是，用少量的组合动作，找出隐藏字符串 $ S $。
你需要实现下面的函数：
std::string guess_sequence(int N)N：串 $S$ 的长度。你的程序可以调用下面的函数：
int press(std::string p)p：你的按键序列。p 必须是长度为从 $0$ 到 $4N$ 的串 (包括 $0$ 和 $4N$)。p 的每个字符必须是 A、B、X 或者 Y。p 后你赚到的金币数量。如果不满足上面的条件，你的程序将被判为 Wrong Answer。否则，你的程序将被判为 Accepted，而你的得分将根据 press 的调用次数来计算。
注意到性质 "$S$ 的首字符不会在串中重复出现"，考虑如何利用这个性质。
那么，设 $S$ 的首字符为 $c$ ($c = S[0]$)，则你的组合动作中，每一个 $c$ 代表一次判定，而不是 $c$ 的不参与判定，且每次判定相当于两个 $c$ 之间的判定和。
什么意思呢？就是，如果你用 "cAB" 拿到了 $x$ 个金币，用 "cXY" 拿到了 $y$ 个金币，则用 "cABcXY" 就可以拿到 $x + y$ 个金币。
我们先通过 $2$ 次询问找到 $c$ 是什么。接下来，我们要依次得到下面那的每个字符，由子任务可以知道，平均每个字符只能有 $1$ 次询问。
我们设当前已知的前缀为 $P$，长度为 $l$，下一个字符可能是 $u, v, w$ (就三种情况)。
如果单独询问，这样就需要询问两次。我们考虑将这两次合并起来询问。
此时，返回值是两个询问的和，因此我们希望有一个询问的答案是 $0$，这样就可以通过另一个询问的答案来判断。
具体地，我们构造 PvPwuPwvPww，那么下一个字符为 $u, v, w$ 当且仅当返回的答案为 $l, l + 1, l + 2$。且询问串长为 $4l + 7 \leq 4n$ 只需 $l \leq n - 2$。
那么，至于最后一个字符，还是通过经典的两次询问解决。
这样，总的询问次数就恰好是 $n + 2$。
时间复杂度 $O \left( n^2 \right)$。
#include "combo.h"
#include <bits/stdc++.h>
using std::string;
string guess_sequence(int n) {
char first = press("AB") ? (press("A") ? 'A' : 'B') : press("X") ? 'X' : 'Y', rem[3] = {'A', 'B', 'X'};
int i, j; string ret(1, first);
if (n == 1) return ret;
for (i = 0; i < 3; ++i) rem[i] == first ? rem[i] = 'Y' : 0;
for (i = 1; i < n - 1; ++i) {
j = press(ret + rem[1] + ret + rem[2] + rem[0] + ret + rem[2] + rem[1] + ret + rem[2] + rem[2]);
ret.push_back(rem[j - i]);
}
ret.push_back(press(ret + rem[0]) == n ? rem[0] : press(ret + rem[1]) == n ? rem[1] : rem[2]);
return ret;
}
坑1：注意特判 $n = 1$ 的情况，此时需要直接 return。