#cspjf2026t2. 回文串(string)

回文串(string)

回文串(string)

题目描述

​ 小 R 有一个长度为 L 的字符串 S=s1…sLS=s_1…s_L,其中只包含小写英文字母。小 R 发现,虽然 S 可能很长,但它可以分成 n 个连续的段,其中第i(1≤i≤n) i(1≤i≤n) 段由 aia_i个小写英文字母 cic_i构成。把这 n 段依次拼接起来便得到 S,因此 L=∑i=1naiL=∑_{i=1}^na_i。相邻两段中的字符可以相同。

​ 小 X 喜欢回文串。若一个字符串反转后与原字符串相同,就称它是回文串,例如 aba、abba 都是回文串,而 aabbc 不是。也就是说,字符串 S 是回文串,当且仅当对于所有i(1≤i≤L) i (1≤i≤L),均有si=sL+1−i s_i=s_{L+1−i}。

​ 小 X 想让小 R 把 S 改成回文串。小 R 可以将 S 中任意一个位置的字符修改成任意小写英文字母。他想用尽量少的修改满足小 X 的要求。

​ 你需要帮助小 R 求出,他最少需要修改多少个位置的字符,才能将 S 改成回文串。

输入格式

​ 从文件 string.in 中读入数据。

​ 输入的第一行包含一个正整数 n。

​ 输入的第 i+1(1≤i≤n)i+1 (1≤i≤n) 行包含一个正整数 aia_i和一个小写英文字母cic_i。

输出格式

​ 输出到文件 string.out 中。

​ 输出一行一个整数,表示小 R 最少需要修改多少个位置的字符,才能将 S 改成回文串。

输入输出样例 #1

3
2 a
2 b
1 c
2

输入输出样例 #2

2
2 a
3 a
0

输入输出样例 #3

6
1000000000 a
1000000000 a
1000000000 a
1000000000 b
1000000000 b
1000000000 b
3000000000

说明/提示

样例 1 解释

​ 小 R 的字符串 S 由 3 段构成:第 1 段由 2 个 a 组成,第 2 段由 2 个 b 组成,第 3 段由 1 个 c 组成,依次拼接得到 S=aabbc。

​ 小 R 可以将最后一个字符 c 和倒数第二个字符 b 都改为 a,得到回文串 aabaa,共修改 2 个位置的字符。可以证明,小 R 最少需要修改 2 个位置的字符,才能将 S 改成回文串。

样例 2 解释

​ 小 R 的字符串 S 由 2 段构成:第 1 段由 2 个 a 组成,第 2 段由 3 个 a 组成,依次拼接得到 S=aaaaa,则 S 已经是回文串,不需要修改。

样例 4

​ 见题目目录下的 string/4.in 与 string/4.ans。

​ 该样例满足测试点 10∼12 的约束条件。

样例 5

​ 见题目目录下的 string/5.in 与 string/5.ans。

​ 该样例满足测试点 13∼16 的约束条件。

样例 6

​ 见题目目录下的 string/6.in 与 string/6.ans。

​ 该样例满足测试点 19∼21 的约束条件。

【数据范围】

对于所有测试数据,均有:

  • 1≤n≤2×1051≤n≤2×10^5;
  • 对于所有 i(1≤i≤n)i(1≤i≤n),均有 1≤ai≤1091≤a_i≤10^9,且 cic_i 为小写英文字母。
测试点编号 n≤ maxi=1nai≤max_{i=1}^na_i≤
1 5
2∼4 2 ^
5,6 10 1
7,8 ^ 50
9 2000 1
10∼12 ^ 50
13∼16 10910^9
17,18 2×1052×10^5 1
19∼21 ^ 500
22∼25 10910^9