梦想星际舰队第10关 && FCOI #7 第三题回文串题解【原创】
本帖最后由 zhangjinxuan 于 2023-8-20 18:58 编辑梦想星际舰队第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
答案与解析
**** Hidden Message *****
最佳战士排行榜
**** Hidden Message ***** 操！我错了，不是子串！
《骗一堆脚本》 根据题目描述，我们需要求出一个字符串S'，它是字符串S的子串，并且是回文串。要求出S'的最长长度。
一种简单的解决方法是使用动态规划。我们可以定义一个二维数组dp，其中dp[ i]表示字符串S从第i个字符到第j个字符（包含两边）所构成的子串是否是回文串。状态转移方程如下：
dp[ i] = dp and S[ i]==S
接下来，我们可以使用两个指针i和j来遍历字符串S的所有可能的子串，并根据dp数组进行判断。我们初始化最长回文串长度为1，然后不断更新最长回文串的长度。
以下是使用Python代码实现的解决方案：
def longestPalindrome(s):
n = len(s)
dp = [ * 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:
if length == 2 or dp:
dp[ i] = True
max_len = max(max_len, length)
return max_len
S = input()
result = longestPalindrome(S)
print(result)
希望对您有所帮助！如果还有其他问题，请随时提问。
如果问题已经解决，请设置最佳答案 这个问题可以通过动态规划来解决。我们可以定义一个二维数组dp，其中dp[ i]表示字符串S从第i个字符到第j个字符之间的子串是否是回文串。
首先，我们可以初始化dp[ i][ i]为True，因为单个字符本身就是回文串。然后，我们遍历字符串S，从长度为2的子串开始，逐渐增加子串的长度。
对于长度为len的子串，我们可以通过判断S[ i]和S是否相等来确定dp[ i]的值。如果S[ i]等于S，那么如果dp为True，说明S[ i]和S之间的子串也是回文串，所以dp[ i]为True。否则，dp[ i]为False。
最后，我们遍历dp数组，找到最长的回文子串长度，即为答案。
下面是具体的代码实现：
def longestPalindrome(s: str) -> int:
n = len(s)
dp = [ * 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:
if length == 2 or dp:
dp[ i] = True
max_len = max(max_len, length)
return max_len
s = input()# 输入字符串S
ans = longestPalindrome(s)
print(ans)
这样，我们就可以得到字符串S的最长回文子串的长度。 看看 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) FCR8第一题、第4题能我写吗（题解）
还有我要投稿FCR9题目{:10_256:} 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;
unordered_map<int, int> cnt;
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
++cnt];
}
for (auto i : cnt) {
res += i.second / 2 * 2;
have |= i.second % 2;
}
printf("%d\n", res + have);
return 0;
} zhangjinxuan 发表于 2023-8-20 19:02
你要投稿你要全负责哦，因为以往多人负责的效果不好
我不是组织比赛
我有空给你一道题，你那个团队重新加一下 sfqxx 发表于 2023-8-20 20:15
我不是组织比赛
你不组织就少了一个参赛的人{:10_256:} zhangjinxuan 发表于 2023-8-20 20:16
你不组织就少了一个参赛的人
？
页:
[1]