6511 - 回文串（string 民间数据）[CSP-J 2026]
小 R 有一个长度为 L 的字符串 S=s_1\ldots s_L，其中只包含小写英文字母。小 R 发现，虽然 S 可能很长，但它可以分成 n 个连续的段，其中第 i\ (1\le i\le n) 段由 a_i 个小写英文字母 c_i 构成。把这 n 段依次拼接起来便得到 S，因此 L=\sum_{i=1}^{n}a_i。相邻两段中的字符可以相同。
小 X 喜欢回文串。若一个字符串反转后与原字符串相同，就称它是回文串，例如 aba、abba 都是回文串，而 aabbc 不是。也就是说，字符串 S 是回文串，当且仅当对于所有 i\ (1\le i\le L)，均有 s_i=s_{L+1-i}。
小 X 想让小 R 把 S 改成回文串。小 R 可以将 S 中任意一个位置的字符修改成任意小写英文字母。他想用尽量少的修改满足小 X 的要求。
你需要帮助小 R 求出，他最少需要修改多少个位置的字符，才能将 S 改成回文串。
从文件 string.in 中读入数据。
输入的第一行包含一个正整数 n。
输入的第 i+1\ (1\le i\le n) 行包含一个正整数 a_i 和一个小写英文字母 c_i。
输出到文件 string.out 中。
输出一行一个整数，表示小 R 最少需要修改多少个位置的字符，才能将 S 改成回文串。
输入
3 2 a 2 b 1 c
输出
2
输入
2 2 a 3 a
输出
0
输入
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=\mathtt{aabbc}。
小 R 可以将最后一个字符 c 和倒数第二个字符 b 都改为 a，得到回文串 aabaa，共修改 2 个位置的字符。可以证明，小 R 最少需要修改 2 个位置的字符，才能将 S 改成回文串。
样例 2 解释
小 R 的字符串 S 由 2 段构成：第 1 段由 2 个 a 组成，第 2 段由 3 个 a 组成，依次拼接得到 S=\mathtt{aaaaa}，则 S 已经是回文串，不需要修改。
样例 4
见题目目录下的 string/4.in 与 string/4.ans。
该样例满足测试点 10\sim12 的约束条件。
样例 5
见题目目录下的 string/5.in 与 string/5.ans。
该样例满足测试点 13\sim16 的约束条件。
样例 6
见题目目录下的 string/6.in 与 string/6.ans。
该样例满足测试点 19\sim21 的约束条件。
数据范围
对于所有测试数据，均有：
- 1\le n\le 2\times10^5；
- 对于所有 i\ (1\le i\le n)，均有 1\le a_i\le10^9，且 c_i 为小写英文字母。
| 测试点编号 | n\le | \max_{i=1}^{n}a_i\le |
|---|---|---|
| 1 | 1 | 5 |
| 2\sim4 | 2 | 5 |
| 5,6 | 10 | 1 |
| 7,8 | 10 | 50 |
| 9 | 2000 | 1 |
| 10\sim12 | 2000 | 50 |
| 13\sim16 | 2000 | 10^9 |
| 17,18 | 2\times10^5 | 1 |
| 19\sim21 | 2\times10^5 | 500 |
| 22\sim25 | 2\times10^5 | 10^9 |
附件下载
string.zip (485.78 KB)
