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

zhangjinxuan

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

第三题：回文串

题目描述

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

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

输入格式
一个字符串S

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

输入输出样例
输入 #1

1. aabaac

复制代码

输出 #1

1. 5

复制代码

输入 #2

1. abcda

复制代码

输出 #2

1. 3

复制代码

输入 #3

1. epfgfhvjzgugptrmwzwawrgcnezbkybxjodtpocgqnuhunykwuclyaaegmkwwitdaduaydkdremaeaausqxnqveoqermalv

复制代码

输出 #3

1. 85

复制代码

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

S 由小写英文字母构成。

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

答案与解析

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

[/hide]

最佳战士排行榜

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

[/hide]

最佳答案

月排行榜 / 总排行榜

sfqxx

2023-8-20 18:49:58

1. s = input()
   
2. a = 0
   
3. b = 0
   
4. for i in set(s):
   
5.     b = s.count(i)
   
6.     if b % 2 == 1:
   
7.         a += 1
   
8. if a <= 1:
   
9.     print(len(s))
   
10. else:
    
11.     print(len(s) - a + 1)

复制代码

跳转到最佳答案楼层

zhangjinxuan

操！我错了，不是子串！

《骗一堆脚本》

陶远航

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

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

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

复制代码

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

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

1. def longestPalindrome(s):
   
2.     n = len(s)
   
3.     dp = [[False] * n for _ in range(n)]
   
4.     max_len = 1
   
5. 
   
6.     # 单个字符是回文串
   
7.     for i in range(n):
   
8.         dp[ i][ i] = True
   
9. 
   
10.     # 遍历所有长度大于1的子串
    
11.     for length in range(2, n+1):
    
12.         for i in range(0, n-length+1):
    
13.             j = i + length - 1
    
14. 
    
15.             # 判断子串是否为回文串
    
16.             if s[ i] == s[j]:
    
17.                 if length == 2 or dp[i+1][j-1]:
    
18.                     dp[ i][j] = True
    
19.                     max_len = max(max_len, length)
    
20. 
    
21.     return max_len
    
22. 
    
23. S = input()
    
24. result = longestPalindrome(S)
    
25. 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数组，找到最长的回文子串长度，即为答案。

下面是具体的代码实现：

1. def longestPalindrome(s: str) -> int:
   
2.     n = len(s)
   
3.     dp = [[False] * n for _ in range(n)]
   
4.     max_len = 1
   
5. 
   
6.     for i in range(n):
   
7.         dp[ i][ i] = True
   
8. 
   
9.     for length in range(2, n+1):
   
10.         for i in range(n - length + 1):
    
11.             j = i + length - 1
    
12.             if s[ i] == s[j]:
    
13.                 if length == 2 or dp[i+1][j-1]:
    
14.                     dp[ i][j] = True
    
15.                     max_len = max(max_len, length)
    
16. 
    
17.     return max_len
    
18. 
    
19. s = input()  # 输入字符串S
    
20. ans = longestPalindrome(s)
    
21. print(ans)
    

复制代码

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

Ewan-Ahiouy

看看

sfqxx

1. s = input()
   
2. a = 0
   
3. b = 0
   
4. for i in set(s):
   
5.     b = s.count(i)
   
6.     if b % 2 == 1:
   
7.         a += 1
   
8. if a <= 1:
   
9.     print(len(s))
   
10. else:
    
11.     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 中选择两个相同的字符累加答案，然后如果有奇数的话，只加一个即可。

代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. int n, x, res, have;
   
5. char s[200002];
   
6. unordered_map<int, int> cnt;
   
7. 
   
8. int main() {
   
9.         scanf("%s", s + 1);
   
10.         n = strlen(s + 1);
    
11.         for (int i = 1; i <= n; ++i) {
    
12.                 ++cnt[s[i]];
    
13.         }
    
14.         for (auto i : cnt) {
    
15.                 res += i.second / 2 * 2;
    
16.                 have |= i.second % 2;
    
17.         }
    
18.         printf("%d\n", res + have);
    
19.         return 0;
    
20. }

复制代码

sfqxx

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

我不是组织比赛

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

zhangjinxuan

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

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

sfqxx

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

？