[已解决]梦想星际舰队第10关 && FCOI #7 第三题回文串题解【原创】

zhangjinxuan

梦想星际舰队第10关 && FCOI #7 题解

第三题：回文串

题目描述

有一个字符串 S，你要求出一个字符串 S'，满足 S' 可以通过 S 中选一些字符组合得出，并且是回文串。

求出 S' 最长可以是多少。

输入格式
一个字符串S

输出格式
一个整数表示答案。

输入输出样例
输入 #1

aabaac

输出 #1

5

输入 #2

abcda

输出 #2

3

输入 #3

epfgfhvjzgugptrmwzwawrgcnezbkybxjodtpocgqnuhunykwuclyaaegmkwwitdaduaydkdremaeaausqxnqveoqermalv

输出 #3

85

数据范围
1≤|S|≤2×10^5

S 由小写英文字母构成。

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U321895

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-20 18:49:58

s = input()
a = 0
b = 0
for i in set(s):
    b = s.count(i)
    if b % 2 == 1:
        a += 1
if a <= 1:
    print(len(s))
else:
    print(len(s) - a + 1)

跳转到最佳答案楼层

zhangjinxuan

操！我错了，不是子串！

《骗一堆脚本》

陶远航

根据题目描述，我们需要求出一个字符串S'，它是字符串S的子串，并且是回文串。要求出S'的最长长度。

一种简单的解决方法是使用动态规划。我们可以定义一个二维数组dp，其中dp[ i][j]表示字符串S从第i个字符到第j个字符（包含两边）所构成的子串是否是回文串。状态转移方程如下：

dp[ i][j] = dp[i+1][j-1] and S[ i]==S[j]

接下来，我们可以使用两个指针i和j来遍历字符串S的所有可能的子串，并根据dp数组进行判断。我们初始化最长回文串长度为1，然后不断更新最长回文串的长度。

以下是使用Python代码实现的解决方案：

def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    max_len = 1

    # 单个字符是回文串
    for i in range(n):
        dp[ i][ i] = True

    # 遍历所有长度大于1的子串
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            j = i + length - 1

            # 判断子串是否为回文串
            if s[ i] == s[j]:
                if length == 2 or dp[i+1][j-1]:
                    dp[ i][j] = True
                    max_len = max(max_len, length)

    return max_len

S = input()
result = longestPalindrome(S)
print(result)

希望对您有所帮助！如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案

isdkz

这个问题可以通过动态规划来解决。我们可以定义一个二维数组dp，其中dp[ i][j]表示字符串S从第i个字符到第j个字符之间的子串是否是回文串。

首先，我们可以初始化dp[ i][ i]为True，因为单个字符本身就是回文串。然后，我们遍历字符串S，从长度为2的子串开始，逐渐增加子串的长度。

对于长度为len的子串，我们可以通过判断S[ i]和S[j]是否相等来确定dp[ i][j]的值。如果S[ i]等于S[j]，那么如果dp[i+1][j-1]为True，说明S[ i]和S[j]之间的子串也是回文串，所以dp[ i][j]为True。否则，dp[ i][j]为False。

最后，我们遍历dp数组，找到最长的回文子串长度，即为答案。

下面是具体的代码实现：

def longestPalindrome(s: str) -> int:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    max_len = 1

    for i in range(n):
        dp[ i][ i] = True

    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[ i] == s[j]:
                if length == 2 or dp[i+1][j-1]:
                    dp[ i][j] = True
                    max_len = max(max_len, length)

    return max_len

s = input()  # 输入字符串S
ans = longestPalindrome(s)
print(ans)

这样，我们就可以得到字符串S的最长回文子串的长度。

Ewan-Ahiouy

看看

sfqxx

s = input()
a = 0
b = 0
for i in set(s):
    b = s.count(i)
    if b % 2 == 1:
        a += 1
if a <= 1:
    print(len(s))
else:
    print(len(s) - a + 1)

sfqxx

FCR8第一题、第4题能我写吗（题解）

还有我要投稿FCR9题目

zhangjinxuan

sfqxx 发表于 2023-8-20 18:51
FCR8第一题、第4题能我写吗（题解）

还有我要投稿FCR9题目

你要投稿你要全负责哦，因为以往多人负责的效果不好

陶远航

首先，我们要从 S 中选字符组成一个回文串，求最大长度。

那么回文串的性质是什么呢，就是回文串的定义，如果记回文串 S 的长度为 N，即每一个 S_i 都与 S_N-i+1 相同，或者每一个 S_i 一定有另外一个相等的字符配对。

既然是 2 个，那么就是，只要是一堆偶数个字符，一定可以组成一个回文串。

也就是说，我们只要在 S 中选取那些有偶数个字符的字符即可。

那么奇数呢？奇数也不能浪费，因为奇数也可以拆分成一个偶数和一个 1，而这个 1，虽然小，但他也能影响答案，回文串的长度可以为奇数，这个 ‘1’ 也就相当于插在了串的中间。

所以，我们的总体思路就是，每次尽可能多的在 S 中选择两个相同的字符累加答案，然后如果有奇数的话，只加一个即可。

代码：

#include <bits/stdc++.h>
using namespace std;

int n, x, res, have;
char s[200002];
unordered_map<int, int> cnt;

int main() {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        for (int i = 1; i <= n; ++i) {
                ++cnt[s[i]];
        }
        for (auto i : cnt) {
                res += i.second / 2 * 2;
                have |= i.second % 2;
        }
        printf("%d\n", res + have);
        return 0;
}

sfqxx

zhangjinxuan 发表于 2023-8-20 19:02
你要投稿你要全负责哦，因为以往多人负责的效果不好

我不是组织比赛

我有空给你一道题，你那个团队重新加一下

zhangjinxuan

sfqxx 发表于 2023-8-20 20:15
我不是组织比赛

你不组织就少了一个参赛的人

sfqxx

zhangjinxuan 发表于 2023-8-20 20:16
你不组织就少了一个参赛的人

？