「KTSC 2024 R2」回文判定 题解
tyukp233
·
·
题解
唯一场切的 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-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$，以验证是否相等。
代码如下。
```cpp
#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;
}
}
```