Palindromes

题目描述

Farmer John 的 United Cows（UCFJ）正在参加一年一度的 hoofball 锦标赛！UCFJ 的队伍由 $N$ 头奶牛组成（$1 \le N \le 7500$），她们在 hoofball 比赛中赢得了金牌，以微弱优势战胜了 Farmer Nhoj 的队伍。 奶牛们已经为颁奖典礼排好了队。她们希望 FJ 拍摄 $\frac{N(N+1)}{2}$ 张合影，每一张对应队列的一个连续子序列。 然而，作为教练的 FJ 对奶牛的站位非常挑剔。具体来说，除非某个子序列构成一个回文，否则他拒绝为其拍照。回文的含义是：对于所有不超过该子序列长度的正整数 $i$，子序列从左端数第 $i$ 头奶牛的品种必须与从右端数第 $i$ 头奶牛的品种相同。每头奶牛的品种要么是 Guernsey，要么是 Holstein。 对于队列的每一个连续子序列（共 $\frac{N(N+1)}{2}$ 个），计算将该子序列重排成回文所需的最少相邻交换次数（如果无法重排成回文，则为 $-1$）。一次相邻交换指的是取子序列中相邻的两头奶牛并交换它们的位置。 输出所有这些最少交换次数之和。 注意：对每个连续子序列所需的交换次数是独立计算的（每次拍照之间奶牛都会回到初始位置）。

输入格式

队列表示为一个长度为 $N$ 的字符串，由字符 G 和 H 组成。

输出格式

输出上述量在队列所有 $\frac{N(N+1)}{2}$ 个连续子序列上的总和。

GHHGGHHGH

12

提示

前四个连续子序列分别为 G、GH、GHH 和 GHHG。G 与 GHHG 已经是回文，因此它们对总和的贡献为 $0$。GHH 可以通过一次相邻交换重排成回文，因此它对总和的贡献为 $1$。GH 无法通过任意次数的相邻交换重排成回文，因此它对总和的贡献为 $-1$。 另一个对子序列总和有贡献的例子是 HHGG。它可以通过两次相邻交换重排成回文。 评分： 除样例外共有十五个测试点，每个测试点对应一个 $N \in [100, 200, 500, 1000, 2000, 5000, 5000, 5000, 5000, 5000, 7500, 7500, 7500, 7500, 7500]$。 题目来源：Mythreya Dharani 和 Benjamin Qi

标签: USACO|2022|Platinum

来源

USACO|2022|Platinum