洛谷-P11240 [KTSC 2024 R2] 回文判定 题解

Solution

我们称 count_pair 为操作 A，find_character 为操作 B。

操作 B 只能做一次，我们考虑先用操作 A 获取尽量多的信息。

对于每次操作 A，为了判断回文性，我们肯定要询问某一对 \(S_i,S_{N-i-1}\) 和另一个数 \(S_k\)。会有 \(3\) 种情况：

1. 返回 \(0\)：\(S_i\neq S_{N-i-1}\)，一定不是回文
2. 返回 \(3\)：\(S_i= S_{N-i-1}\)
3. 返回 \(1\)：此时 \(S_i= S_{N-i-1}\) 等价于 \(S_k\notin \{S_i,S_{N-i-1}\}\)

注意到情况 \(3\) 的等价条件符合操作 B 的形式。这启发我们得到如下做法：

首先做 \(\lfloor N/2\rfloor-1\) 次操作 A。固定上面的 \(k=0\)，遍历 \(1\le i<\lfloor N/2\rfloor\)，询问 \(S_i,S_{N-i-1},S_0\)。然后分讨 \(3\) 种情况，分别把使得返回值为 \(1\) 和 \(3\) 的数对 \(i,N-i-1\) 扔进 vector<int> p,q（参考代码实现）。

此时操作 B 就派上用场了。我们询问 find_character(0,p)。根据等价条件，如果返回 \(0\) ，则 \(\forall i\) 有 \(S_i=S_{N-i-1}\)，否则序列一定不回文。

此时一定有 p 中的数 \(\neq S_0\) 而 q 中的数 \(=S_0\)。我们需要用 \(2\) 次操作 A 判断是否有 \(S_0=S_{N-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)。不难得出 \(S_0=S_{N-1}\) 当且仅当前者返回值 \(\neq3\) 且后者返回值 \(\neq0\)。

Code

#include <vector>
#define eb emplace_back
using namespace std;
extern int count_pair(int,int,int);
extern int find_character(int,vector<int>);
int guess_palindromicity(int N){vector<int> p,q;for(int i=1,j=N-2;i<(N>>1);++i,--j){int k=count_pair(0,i,j);if(!k) return 0;k==1?(p.eb(i),p.eb(j)):(q.eb(i),q.eb(j));}if(p.size()&&find_character(0,p)) return 0;if(q.size()) return count_pair(q[0],0,N-1)==3;return count_pair(p[0],p[1],N-1)!=3&&count_pair(p[0],0,N-1);
}