回文串
本题需要文件读写
文件 IO 为:输入文件
string.in,输出文件string.out。请使用上述文件名读入和输出。
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
问题描述
小 R 有一个只包含小写英文字母的字符串 。它按顺序分成 个连续的段,第 段由 个相同的小写英文字母 组成。将这 段依次拼接,就得到 ,其长度为
注意,相邻两段的字符可以相同。
如果一个字符串反转后与原字符串相同,就称它为回文串。例如 aba、abba 是回文串,而 aabbc 不是。
小 R 可以将 中任意位置的字符修改成任意小写英文字母。请计算最少需要修改多少个位置的字符,才能将 变成回文串。
输入格式
从文件 string.in 中读入数据。
第一行输入一个正整数 ,表示段数。
接下来 行,第 行输入一个正整数 和一个小写英文字母 ,表示第 段的长度和字符。
输出格式
输出到文件 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,共修改 个位置,且不存在修改更少的方案。
样例 2 的字符串为 aaaaa,已经是回文串。
评测数据规模
对于所有数据,保证:
- ;
- ;
- 是小写英文字母。
| 测试点编号 | ||
|---|---|---|
本题共 个独立测试点,每点 分。
无金币奖励
CSP-J2026估分(民间数据)
- 状态
- 已结束
- 规则
- IOI
- 题目
- 4
- 开始于
- 2026-10-31 17:00
- 结束于
- 2026-11-9 1:00
- 持续时间
- 200 小时
- 主持人
- 参赛人数
- 11