Description
Idea
我们需要一种能一次确定一位的高效询问算法。
考虑到 $p$ 的最大长度为 $4n$，$S$ 的首字母只出现一次，那么我们每次可以基于已知的前缀 $s$，询问 $4$ 种可能的情况。
不妨设 $S$ 的首字母为 $A$，对于已知的前缀 $s$，我们询问
$$sXBsXXsXYsB$$
如果返回值比当前长度大 $2$，说明下一位是 $X$；大 $1$，说明下一位是 $B$，否则下一位为 $Y$。
对开头和结尾的两个字符做二分查找，总询问次数为 $n+2$。
Code
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include "combo.h" #include <vector> int head,len=1; void start(); void end(int N); std::string c="ABXY",S,id; std::vector<std::string>h[4]; std::string generate_press(){ return S+id[0]+S+id[1]+id[0]+ S+id[1]+id[1]+S+id[1]+id[2]; } std::string guess_sequence(int N){ start(); while(len<N-1){ int opt=press(generate_press())-len; S+=id[(opt+2)%3];++len; } if (len==N-1) end(N); return S; } void start(){ S=id=""; if (press("AB")){ if (press("A")) S+=c[head=0]; else S+=c[head=1]; } else{ if (press("X")) S+=c[head=2]; else S+=c[head=3]; } for (int i=0;i<4;++i) if (i!=head) id+=c[i]; } void end(int N){ if (press((S+id[0]+S+id[1]))==N){ if (press((S+id[0]))==N) S+=id[0]; else S+=id[1]; } else S+=id[2]; } |