P17828 [CSP-J 2026] 回文串 / string

题目描述

小 R 有一个长度为的字符串，其中只包含小写英文字母。小 R 发现，虽然可能很长，但它可以分成个连续的段，其中第段由个小写英文字母构成。把这段依次拼接起来便得到，因此。相邻两段中的字符可以相同。

小 X 喜欢回文串。若一个字符串反转后与原字符串相同，就称它是回文串，例如 aba、abba 都是回文串，而 aabbc 不是。也就是说，字符串是回文串，当且仅当对于所有，均有。

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

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

输入格式

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

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

输入的第行包含一个正整数和一个小写英文字母。

输出格式

输出到文件 string.out 中。

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

输入输出样例 #1

输入 #1

3
2 a
2 b
1 c

输出 #1

输入输出样例 #2

输入 #2

2
2 a
3 a

输出 #2

输入输出样例 #3

输入 #3

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

输出 #3

3000000000

说明/提示

样例 1 解释

小 R 的字符串由段构成：第段由个 a 组成，第段由个 b 组成，第段由个 c 组成，依次拼接得到。

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

样例 2 解释

小 R 的字符串由段构成：第段由个 a 组成，第段由个 a 组成，依次拼接得到，则已经是回文串，不需要修改。

样例 4

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

该样例满足测试点的约束条件。

样例 5

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

该样例满足测试点的约束条件。

样例 6

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

该样例满足测试点的约束条件。

数据范围

对于所有测试数据，均有：

；
对于所有，均有，且为小写英文字母。

::cute-table{tuack}

测试点编号

题解:

#include<iostream>
using namespace std;
int a[200001];
char c[200001];
int main()
{
    int n;
    long long ans=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>c[i];
    }
    int i=1,j=n;
    while(i<j)
    {
        if(c[i]!=c[j])
        {
            if(a[i]>a[j])
            {
                ans+=a[j];
                a[i]-=a[j];
                j--;
            }
            else if(a[i]<a[j])
            {
                ans+=a[i];
                a[j]-=a[i];
                i++;
            }
            else
            {
                ans+=a[i];
                i++;
                j--;
            }
        }
        else
        {
            if(a[i]>a[j])
            {
                a[i]-=a[j];
                j--;
            }
            else if(a[i]<a[j])
            {
                a[j]-=a[i];
                i++;
            }
            else
            {
                i++;
                j--;
            }
        }
    }
    cout<<ans;
    return 0;
}