B. 回文串

    传统题 文件IO:string 1000ms 1024MiB

回文串

本题需要文件读写

文件 IO 为:输入文件 string.in,输出文件 string.out。请使用上述文件名读入和输出。

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

小 R 有一个只包含小写英文字母的字符串 SS。它按顺序分成 nn 个连续的段,第 ii 段由 aia_i 个相同的小写英文字母 cic_i 组成。将这 nn 段依次拼接,就得到 SS,其长度为

L=∑i=1nai.L=\sum_{i=1}^{n}a_i.

注意,相邻两段的字符可以相同。

如果一个字符串反转后与原字符串相同,就称它为回文串。例如 aba、abba 是回文串,而 aabbc 不是。

小 R 可以将 SS 中任意位置的字符修改成任意小写英文字母。请计算最少需要修改多少个位置的字符,才能将 SS 变成回文串。

输入格式

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

第一行输入一个正整数 nn,表示段数。

接下来 nn 行,第 ii 行输入一个正整数 aia_i 和一个小写英文字母 cic_i,表示第 ii 段的长度和字符。

输出格式

输出到文件 string.out。

输出一行一个整数,表示最少需要修改的位置数量。

样例输入 1

3
2 a
2 b
1 c

样例输出 1

2

样例输入 2

2
2 a
3 a

样例输出 2

0

样例输入 3

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

样例输出 3

3000000000

说明

样例 1 的字符串为 aabbc。把最后一个字符 c 和倒数第二个字符 b 都改为 a,可得到回文串 aabaa,共修改 22 个位置,且不存在修改更少的方案。

样例 2 的字符串为 aaaaa,已经是回文串。

评测数据规模

对于所有数据,保证:

  • 1≤n≤2×1051\le n\le2\times10^5;
  • 1≤ai≤1091\le a_i\le10^9;
  • cic_i 是小写英文字母。
测试点编号 n≤n\le max⁡ai≤\max a_i\le
11 55
2∼42\sim4 22
5,65,6 1010 11
7,87,8 5050
99 20002000 11
10∼1210\sim12 5050
13∼1613\sim16 10910^9
17,1817,18 2×1052\times10^5 11
19∼2119\sim21 500500
22∼2522\sim25 10910^9

本题共 2525 个独立测试点,每点 44 分。

无金币奖励

CSP-J2026估分(民间数据)

未参加
状态
已结束
规则
IOI
题目
4
开始于
2026-10-31 17:00
结束于
2026-11-9 1:00
持续时间
200 小时
主持人
参赛人数
11