自动搬运

查看原文

来自洛谷，原作者为

	tyukp233 **

搬运于2025-08-24 23:05:36，当前版本为作者最后更新于2024-10-29 17:26:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

唯一场切的 KTSC 题。

首先看到 count_pair 函数的调用次数 $A\le\ \lfloor\frac{N}{2}\rfloor+1$，如果传入的参数可以相同，那就：

for(int i=0;i<N/2;i++){
  if(count_pair(i,N-i-1,N-i-1)==1)return 0;
}
return 1;

可惜不行。

但我们有一个初步的想法，就是让第三个参数一直为同一个位置，这样就控制了变量，我选择从两边判到中间，取第三个参数为 $\lfloor\frac{N}{2}\rfloor$。

count_pair 函数的返回值只有 $0$，$1$，$3$。

• 返回值为 $0$，$S_i$ 和 $S_{N-i-1}$ 不可能相等。
• 返回值为 $1$，不知道是 $S_i=S_{N-i-1}\neq S_{\lfloor\frac{N}{2}\rfloor}$，还是 $S_i\neq S_{n-i-1}$ 且 $S_{\lfloor\frac{N}{2}\rfloor}\in \set{S_i,S_{n-i-1}}$。
• 返回值为 $3$，$S_i=S_{N-i-1}=S_{\lfloor\frac{N}{2}\rfloor}$。

这下就可以使用 find_character 函数判断 $S_{\lfloor\frac{N}{2}\rfloor}$ 是否与上面返回 $1$ 的位置的数相等了。用 vector 记录下来即可。

vector<int> tmp;
for(int i=0,res;i<N/2;i++){
	res=count_pair(i,N-i-1,N>>1);
	if(res==0)return 0;
	if(res==1)tmp.push_back(i),tmp.push_back(n-i-1);
}
if(!tmp.empty()){
	if(find_character(n>>1,tmp))return 0;
}

然后处理 $S_{\lfloor\frac{N}{2}\rfloor}$。

$N$ 为奇数好办，不用额外判断，$S_{\lfloor\frac{N}{2}\rfloor}$ 自己和自己回文。

$N$ 为偶数时 $S_{\lfloor\frac{N}{2}\rfloor-1}$ 还没与 $S_{\lfloor\frac{N}{2}\rfloor}$ 判断是否相等。考虑前面我们知道 $S_i=S_{N-i-1}$，随便取出一组检查一下，将 $S_{\lfloor\frac{N}{2}\rfloor}$ 换成 $S_{\lfloor\frac{N}{2}\rfloor-1}$ 结果是否相等。当然两者结果都为 $1$ 时，只能说明 $S_{\lfloor\frac{N}{2}\rfloor}\neq S_i$ 且 $S_{\lfloor\frac{N}{2}\rfloor-1}\neq S_i$，我们还要让 count_pair 在 $S_{\lfloor\frac{N}{2}\rfloor-1}$ 和 $S_{\lfloor\frac{N}{2}\rfloor}$ 以外多加一个参数 $i$，以验证是否相等。

代码如下。

#include<bits/stdc++.h>
#include "palindrome.h"
using namespace std;
int guess_palindromicity(int n){
	vector<int> tmp;
	if(n&1){
		for(int i=0,res;i<(n-1>>1);i++){
			res=count_pair(n>>1,i,n-i-1);
			if(res==0)return 0;
			if(res==1)tmp.push_back(i),tmp.push_back(n-i-1);
		}
		if(!tmp.empty()){
			if(find_character(n>>1,tmp))return 0;
		}
		return 1;
	}else {
		int c=0;
		for(int i=0,res;i<(n-1>>1);i++){
			res=count_pair(n>>1,i,n-i-1);
			if(res==0)return 0;
			if(res==1)tmp.push_back(i),tmp.push_back(n-i-1);
			if(i==0)c=res;
		}
		if(!tmp.empty()){
			if(find_character(n>>1,tmp))return 0;
		}
		if(count_pair(0,n-1>>1,n>>1)==0||count_pair(n-1,n-1>>1,0)!=c)return 0;
		return 1;
	}
}