P9606 [CERC2019] ABB
题目背景
题目译自 CERC 2019 「ABB」
题目描述
Fernando 受雇于滑铁卢大学，负责完成该大学不久前开始的一个开发项目。在校园外，该大学希望为重要的外国游客和合作者建造具有代表性的平房街。
目前，这条街只建了一部分，它从湖岸开始，一直延伸到森林尽头。Fernando 的任务是通过在森林尽头建造更多的平房来完成这条街。所有现有的平房都坐落在街道的一侧，新的平房应该建在同一侧。这些平房有各种各样的类型，漆成各种各样的颜色。
在 Fernando 看来，整条街的布局有点混乱。他担心增加新平房后，它会看起来更加混乱。所以他想通过为新平房选择合适的颜色来增加一些排列顺序。当项目完成时，平房的整个颜色序列将是对称的，也就是说，从街道的两端观察时，颜色序列是相同的。
在其他问题中，Fernando 想知道，在满足平房颜色限制的情况下，他最少需要用来建造和适当染色才能完成项目的新平房数量。
简要题意
求使给定小写字母字符串成为回文串需在字符串末尾加入字母的最少数量。
输入格式
第一行包含一个整数
N
(
1
≤
N
≤
4
×
10
5
)
N\\ (1\\le N\\le 4\\times 10^5)
N (1≤N≤4×105)，代表街道上现有平房的数量。
第二行包含一个由
N
N
N 个小写字母（从 a 到 z）组成的字符串，代表从湖岸开始的街道现有的平房颜色顺序，其中不同的字母表示不同的颜色。
输出格式
输出一个整数，代表满足 Fernando 要求的新平房的最少数量。
输入输出样例 #1
输入 #1
3
abb
输出 #1
1
输入输出样例 #2
输入 #2
12
recakjenecep
输出 #2
11
输入输出样例 #3
输入 #3
15
murderforajarof
输出 #3
6
C++实现
#include<iostream>
using namespace std;
int n,len,maxx;
int f[4000005];
string ss;
char s[8000005];
int main()
{
cin>>len>>ss;
n=(len<<1)+1;
for(int i=0,j=len–1;i<n;i++)
s[i]=i&1?ss[j—]:'#';
for(int i=0,c=0,r=0;i<n;i++)
{
f[i]=r>i?min(f[(c<<1)–i],r–i):1;
while(i–f[i]>=0&&i+f[i]<n&&s[i–f[i]]==s[i+f[i]])
f[i]++;
if(i+f[i]>r)
r=i+f[i],c=i;
if(f[i]==i+1)
maxx=f[i]–1;
}
cout<<len–maxx;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
