Solution我们称count_pair为操作 Afind_character为操作 B。操作 B 只能做一次我们考虑先用操作 A 获取尽量多的信息。对于每次操作 A为了判断回文性我们肯定要询问某一对Si,SN−i−1S_i,S_{N-i-1}Si​,SN−i−1​和另一个数SkS_kSk​。会有333种情况返回000Si≠SN−i−1S_i\neq S_{N-i-1}Si​SN−i−1​一定不是回文返回333SiSN−i−1S_i S_{N-i-1}Si​SN−i−1​返回111此时SiSN−i−1S_i S_{N-i-1}Si​SN−i−1​等价于Sk∉{Si,SN−i−1}S_k\notin \{S_i,S_{N-i-1}\}Sk​∈/{Si​,SN−i−1​}注意到情况333的等价条件符合操作 B 的形式。这启发我们得到如下做法首先做⌊N/2⌋−1\lfloor N/2\rfloor-1⌊N/2⌋−1次操作 A。固定上面的k0k0k0遍历1≤i⌊N/2⌋1\le i\lfloor N/2\rfloor1≤i⌊N/2⌋询问Si,SN−i−1,S0S_i,S_{N-i-1},S_0Si​,SN−i−1​,S0​。然后分讨333种情况分别把使得返回值为111和333的数对i,N−i−1i,N-i-1i,N−i−1扔进vectorint p,q参考代码实现。此时操作 B 就派上用场了。我们询问find_character(0,p)。根据等价条件如果返回000则∀i\forall i∀i有SiSN−i−1S_iS_{N-i-1}Si​SN−i−1​否则序列一定不回文。此时一定有p中的数≠S0\neq S_0S0​而q中的数S0S_0S0​。我们需要用222次操作 A 判断是否有S0SN−1S_0S_{N-1}S0​SN−1​。如果q非空判断count_pair(q[0],0,N-1)3即可。否则p一定非空。我们询问count_pair(p[0],p[1],N-1)和count_pair(p[0],0,N-1)。不难得出S0SN−1S_0S_{N-1}S0​SN−1​当且仅当前者返回值≠3\neq33且后者返回值≠0\neq00。Code#includevector#defineebemplace_backusingnamespacestd;externintcount_pair(int,int,int);externintfind_character(int,vectorint);intguess_palindromicity(intN){vectorintp,q;for(inti1,jN-2;i(N1);i,--j){intkcount_pair(0,i,j);if(!k)return0;k1?(p.eb(i),p.eb(j)):(q.eb(i),q.eb(j));}if(p.size()find_character(0,p))return0;if(q.size())returncount_pair(q[0],0,N-1)3;returncount_pair(p[0],p[1],N-1)!3count_pair(p[0],0,N-1);}