「KTSC 2024 R2」回文判定 题解

问题分析

我们需要在只能使用两种特殊机器的情况下，判断序列 $S$ 是否是回文。关键在于最小化机器调用次数，特别是要争取只使用 count_pair 机器。

算法思路：对称性检测 + 分类讨论

核心观察

对于回文序列，对称位置 $i$ 和 $n-1-i$ 的值必须相等。我们通过检查对称位置的值关系来判断回文性。

1. 主循环：检查对称位置三元组

vector<int> bug;
int equ = -1;

for (int i = 0; i < (n + 1) / 2 - 1; ++i)
    switch (count_pair(i, (n + 1) / 2 - 1, n - i - 1)) {
    case 0:
        return 0;  // 立即发现不对称

    case 3:
        equ = i;   // 记录全等的位置
        break;

    case 1:
        bug.push_back(i), bug.push_back(n - i - 1);  // 记录可疑位置
    }

算法逻辑：

• 检查三元组 $(i, \text{mid}, n-1-i)$，其中 $\text{mid} = \lfloor\frac{n+1}{2}\rfloor - 1$
• case 0：三个值都不同，肯定不是回文
• case 3：三个值全相等，记录为参考点
• case 1：有一对相等的值，记录可疑位置

2. 奇数长度序列处理

if (n % 2 == 1)
    return !(bug.size() && find_character((n + 1) / 2 - 1, bug) != 0);

原理：

• 如果存在可疑位置，检查中心元素是否与任何可疑位置的值相等
• 如果相等，说明对称性被破坏，不是回文

3. 偶数长度序列处理

情况1：中心附近有可疑位置

if (bug.size() && find_character((n + 1) / 2, bug) != 0)
    return 0;

检查中心右侧元素是否与可疑位置的值相等。

情况2：没有全等参考点

if (equ == -1) {
    if (!count_pair((n + 1) / 2 - 1, (n + 1) / 2, bug[0]))
        return 0;
    return count_pair((n + 1) / 2, bug[0], bug[1]) == 1;
}

通过检查中心两个元素与可疑位置的关系来判断。

情况3：有全等参考点

return count_pair((n + 1) / 2 - 1, (n + 1) / 2, equ) == 3;

检查中心两个元素是否与参考点全等。

代码实现详解

关键变量

vector<int> bug;    // 存储可疑的对称位置
int equ = -1;       // 存储全等的位置索引

主循环分析

for (int i = 0; i < (n + 1) / 2 - 1; ++i)
    switch (count_pair(i, (n + 1) / 2 - 1, n - i - 1)) {
    // 检查位置i、中心、对称位置n-1-i的值关系
    }

调用次数：$\lfloor\frac{n}{2}\rfloor - 1$ 次，满足 $A \leq \lfloor\frac{n}{2}\rfloor + 1$ 的要求。

机器调用优化

count_pair 调用模式

• 主循环：$\lfloor\frac{n}{2}\rfloor - 1$ 次
• 后续检查：最多 2 次
• 总计：$\lfloor\frac{n}{2}\rfloor + 1$ 次，达到最优

find_character 调用模式

find_character((n + 1) / 2 - 1, bug)  // 最多1次
find_character((n + 1) / 2, bug)      // 最多1次  

算法正确性证明

回文必要条件

对于回文序列，必须满足：

$1.$ 所有对称位置的值相等：$S[i] = S[n-1-i]$

$2.$ 中心对称性（偶数长度时中心两个值相等）

算法覆盖所有情况

$1.$ 立即否决：发现三个不同值

$2.$ 全等情况：利用全等位置推断中心关系

$3.$ 部分相等：通过可疑位置交叉验证

复杂度分析

• count_pair 调用：$O(\frac{n}{2})$，达到理论最优
• find_character 调用：$O(1)$，仅在最坏情况下使用
• 空间复杂度：$O(n)$ 存储可疑位置

算法优势

$1.$ 最优调用次数：达到理论下界的 $\lfloor\frac{n}{2}\rfloor + 1$ 次

$2.$ 尽早终止：发现不对称立即返回

$3.$ 分类精细：处理各种边界情况

$4.$ 资源节约：最小化 find_character 使用

该解法通过巧妙的对称性检查和精细的情况分类，在严格限制下高效解决了回文判定问题。