P7034: 回文

---

【题目描述】

【题目描述】
农夫约翰合牛国（The United Cows of Farmer John，UCFJ）正在参加一年一度的蹄球锦标赛！UCFJ 队的 N（1≤N≤7500）头奶牛以微弱优势击败了 Farmer Nhoj 的队伍，赢得了蹄球比赛的金牌。
奶牛们已经为颁奖典礼排好了队。她们希望 FJ 拍摄 N(N+1)/2 张合影，为队伍的每个连续子段拍摄一张。
然而，FJ，作为球队的主帅，对于奶牛们应该如何列队十分讲究。具体地说，他拒绝为一个子段拍照，除非它形成一个*回文串*，即对于所有不超过子段长度的正整数 ii，从子段左端开始的第 ii 头奶牛的品种必须与从子段右端开始的第 ii 头奶牛的品种相同。每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。
对于队伍的 N(N+1)/2 个连续子段的每一个，计算将该子段重新排列成回文串所需的最小换位次数（如果不可能这样做则为 −1）。单次换位是在子序列中取两头相邻的奶牛并交换。输出所有这些次数之和。
注意对每个连续子段所需的换位次数是独立计算的（奶牛们会在照片拍摄之间返回她们的起始位置）。
【输入格式】（从终端 / 标准输入读入）：
输入队伍，用一个长为 N 的字符 G 和 H 组成的字符串表示。
【输出格式】（输出至终端 / 标准输出）：
输出队伍的所有 N(N+1)/2 个连续子段的前述数量之和。
【输入样例】：
GHHGGHHGH
【输出样例】：
12
【样例说明】
前四个连续子段是 G，GH，GHH 和 GHHG。G 和 GHHG 都已经是回文串，因此它们对总和的贡献为 0。GHH 可以使用一次换位重新排列成回文串，因此它对总和的贡献为 1。GH 不能使用任意次数的换位重新排列成回文串，因此它对总和的贡献为 −1。
HHGG 是另一个对总和有贡献的连续子段。这个子段可以使用两次换位重新排列成回文串。
【测试点性质】：
除样例外有十五个测试点，满足 N∈[100,200,500,1000,2000,5000,5000,5000,5000,5000,7500,7500,7500,7500,7500] 各一。
 

题目类型~

USACO-2022-铂金-12 

咻咻~

提交答案 状态 返回