打卡信奥刷题（3361）用C++实现信奥题 P9606 [CERC2019] ABB

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 NN个小写字母从a到z组成的字符串代表从湖岸开始的街道现有的平房颜色顺序其中不同的字母表示不同的颜色。输出格式输出一个整数代表满足 Fernando 要求的新平房的最少数量。输入输出样例 #1输入 #13 abb输出 #11输入输出样例 #2输入 #212 recakjenecep输出 #211输入输出样例 #3输入 #315 murderforajarof输出 #36C实现#includeiostreamusingnamespacestd;intn,len,maxx;intf[4000005];string ss;chars[8000005];intmain(){cinlenss;n(len1)1;for(inti0,jlen-1;in;i)s[i]i1?ss[j--]:#;for(inti0,c0,r0;in;i){f[i]ri?min(f[(c1)-i],r-i):1;while(i-f[i]0if[i]ns[i-f[i]]s[if[i]])f[i];if(if[i]r)rif[i],ci;if(f[i]i1)maxxf[i]-1;}coutlen-maxx;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容