题解：P14730 [ICPC 2022 Seoul R] Palindrome Type

_ruyingsuixing_ · 2025-12-13 09:58:31 · 题解

P14730 [ICPC 2022 Seoul R] Palindrome Type 题解

纯享阅读区
题目传送门

总体分析

核心：修改字符串 s 使其成为回文串，记最小次数为 k，如果 k\leq3，输出 k，否则输出 -1。

因此，可以从 k=0\sim3 依次进行 DFS 搜索，只要有一次成功，输出 k，结束。

思路引导

:::warning[提问]{open} 如何 DFS 搜索修改过程算出 k？ :::

:::success[DFS 函数]{open} 使用 双指针。

当 l<r 时：

• 如果左指针 l 和右指针 r 对应的 s_l=s_r，那么这部分已经是回文的，l 向右移，r 向左移。
• 否则：
  • 如果剩余次数 step=0，无法继续修改，返回无法完成。
  • 如果删除 l+1 或 r+1 可完成，返回可以完成。
  • 否则返回无法完成。

返回无法完成。 :::

:::error[警告] 如果 k\leq 3 都不可以，最后输出 -1。 :::

核心代码

bool dfs(int l,int r,int step){
    while(l<r){
        if(s[l]==s[r])l++,r--;
        else{
            if(!step)return 0;
            if(dfs(l+1,r,step-1)||dfs(l,r-1,step-1))return 1;
            return 0;
        }
    }
    return 1;
}