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

jiangshengcheng_602 · 2025-12-13 10:29:54 · 题解

题目大意

• 判断字符串 v 能否通过删除最少数量的字符变成回文串，且最少除数 k 是否在 \{0,1,2,3\} 中。输出最小满足的 k ，若都不满足输出 -1 。

  算法

• 考虑用双指针 l , r 两端向中间匹配，删除次数上限为 k 。
• 因为只关心 k\le 3 ，可以对不相等处进行最多
• 为避免重复计算，用记忆化记录失败的状态。

  时间复杂度

• 每次匹配走过的字符共为 O(n)，分支数上线为 2^k，因此总时间约 O(2^kn)，对 k\le 3 即 O(n) 量级，能在 n\le 10^5 内通过。

最后附上代码：

#include <iostream>
#include <unordered_set>
using namespace std;
typedef long long ll;
string s;
int n;
unordered_set<ll>bad;
bool can(int l,int r,int ans)
{
    while(l<r and s[l]==s[r]){l++;r--;}
    if(l>=r)return true;
    if(ans==0)return false;
    ll key=((ll)l<<40)|((ll)r<<2)|ans;
    if(bad.count(key))return false;
    if(can(l+1,r,ans-1))return true;
    if(can(l,r-1,ans-1))return true;
    bad.insert(key);
    return false;
}
int main()
{
    cin>>s;
    n=s.size();
    for (int k=0;k<=3;k++)
    {
        bad.clear();
        if(can(0,n-1,k))return cout<<k,0;
    }
    cout<<-1;
    return 0;
}