欢乐赛#68 T3 题解

感觉作为 T3 有点超标？

先解释下样例：
将abCcbq改为QBCCbq，最少修改 $2$ 次。

用 Q&A 格式写个题解。

Q1：怎么记录答案？
A1：注意到 $n\le2\times10^5$，空间复杂度 $\text O(n)$ 足够，可以开个数组 $f$，$f_i$ 记录 $s_i$ 是否需要修改。

Q2：怎么判断是否满足大小写要求？
A2：这就很简单了，不满足前两条规则的字符一定要修改。

Q3：怎么判断不满足回文要求的两个字符修改哪一个？
A3：尽可能修改不满足前两条规则的字符。如果没有修改哪个都行。

注：代码中含有压行成分。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,ans;
string s;
bool f[N];//1 表示需要修改
int main(){
    cin>>s;
    n=s.size();
    for (int i=0;i*2<n;i++){
        if (s[i]>='a'){//规则1
            f[i]=1;
        }
    }
    for (int i=n/2;i<n;i++){
        if (s[i]<='Z'){//规则2
            f[i]=1;
        }
        if (s[i]+('a'-'A')*(s[i]<='Z')!=s[n-i-1]+('a'-'A')*(s[n-i-1]<='Z')){//规则3，忽略大小写后不相等
            if (!f[i]){//如果 f[i] 为 0，不管 f[n-i-1] 的值是多少都可以修改
                f[n-i-1]=1;
            }//如果 f[i] 为 1，则修改 s[i] 无需操作
        }
    }
    for (int i=0;i<n;i++){
        ans+=f[i];
    }
    cout<<ans;
	return 0;
}