旺崽的博客

要么天赋异禀，要么天道酬勤

0%

第十八届浙大城市学院程序设计竞赛（同步赛） F.Palindrome

发表于 分类于 Valine：

题目链接

题目描述

You are given a string $s{}$​ of $n{}$ lowercase letters.
You have to delete exactly two letters from $s{}$, determine whether the string can become a palindrome after the change.
Definition of palindrome: If a string $s{}$ of $n{}$ lowercase letters is a palindrome, then for each $s_i(1\leq i\leq n),s_i=s{n-i+1}$ .
For example, “ababa” and “abba” are palindromes, but “abab” not.

输入描述:

The first line contains an integer $t(1\leq t\leq10^3)$ — the number of test cases.
For each test case, the first line contains an integer $n(3\leq n\leq 2!\cdot!10^3)$ representing the length of $s{}$, the second line contains a string of length $n{}$.
It is guaranteed that the sum of $n{}$ for all test cases does not exceed $10^4{}$.

输出描述:

If it is possible to change the string into a palindrome after deleting two letters from $s_{}$, please output “Yes”, otherwise output “No”.

示例1

输入

1
2
3
4
5
6
7
3
4
abca
6
ababab
6
abcabc

输出

1
2
3
Yes
Yes
No

自己手写几个例子很容易发现修改不超过 2 次的能构成回文串的字符串都可以，简单说明一下：

  1. 本身是回文串，开头结尾各删一个即可
  2. 删掉一个字符构成回文串，此时的回文串不管长度是奇数还是偶数，删掉中间的那个字符还是回文串

所以我们只需要用 DFS 暴力删除即可，如果删除次数超过 2 返回 0，否则返回 1，在 DFS 的过程中维护两个指针即可，复杂度 $O(4*n)$，AC 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include "bits/stdc++.h"

using namespace std;
int n, t;
string s;

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

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> s;
        if (dfs(0, n-1, 2)) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}