A175517.[CSP-J 2026] 回文串(文件读写)
普及-
通过率:0%
时间限制:1.00s
内存限制:1024MB
题目描述
小 R 有一个长度为 L 的字符串 S=s1…sL,其中只包含小写英文字母。小 R 发现,虽然 S 可能很长,但它可以分成 n 个连续的段,其中第 i (1≤i≤n) 段由 ai 个小写英文字母 ci 构成。把这 n 段依次拼接起来便得到 S,因此 L=∑i=1nai。相邻两段中的字符可以相同。
小 X 喜欢回文串。若一个字符串反转后与原字符串相同,就称它是回文串,例如 aba、abba 都是回文串,而 aabbc 不是。也就是说,字符串 S 是回文串,当且仅当对于所有 i (1≤i≤L),均有 si=sL+1−i。
小 X 想让小 R 把 S 改成回文串。小 R 可以将 S 中任意一个位置的字符修改成任意小写英文字母。他想用尽量少的修改满足小 X 的要求。
你需要帮助小 R 求出,他最少需要修改多少个位置的字符,才能将 S 改成回文串。
输入格式
从文件 string.in 中读入数据。
输入的第一行包含一个正整数 n。
输入的第 i+1 (1≤i≤n) 行包含一个正整数 ai 和一个小写英文字母 ci。
输出格式
输出到文件 string.out 中。
输出一行一个整数,表示小 R 最少需要修改多少个位置的字符,才能将 S 改成回文串。
输入输出样例
输入#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 解释
小 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×105;
- 对于所有 i (1≤i≤n),均有 1≤ai≤109,且 ci 为小写英文字母。
| 测试点编号 | n≤ | maxi=1nai≤ |
|---|---|---|
| 1 | 1 | 5 |
| 2∼4 | 2 | 5 |
| 5,6 | 10 | 1 |
| 7,8 | 10 | 50 |
| 9 | 2000 | 1 |
| 10∼12 | 2000 | 50 |
| 13∼16 | 2000 | 109 |
| 17,18 | 2×105 | 1 |
| 19∼21 | 2×105 | 500 |
| 22∼25 | 2×105 | 109 |
附件
输入解题思路,AI测评打分。不知道怎么写?