在洛谷上阅读
Part 0 题意简述
原题这场月赛我唯一AC的题
给出一个字符串 \(S\)，令 \(T=S\)，求使用 \(S\) 的子串插入 \(T\)，将 \(T\) 变形的最少的操作次数。且字符串 \(S\) 会被修改 \(q\) 次。
具体变形：
\(S=\overline{s_1s_2…s_n}\)，经过变形，使 \(T=\overline{s_1s_1s_2s_2…s_ns_n}\)。
看不懂？去看样例解释。
Part 1 题目分析
那么看过样例，我们可以知道：
对于 \(S=T=\texttt{aabc}\)，我们可以分别插入子串 \(\texttt{aa}\) 和 \(\texttt{bc}\) 或分别插入子串 \(\texttt{aab}\) 和 \(\texttt{c}\)，而这两种操作所用次数相同。
那么分析这两种操作的共同特点，我们可以得出每次最多可以插入的子串特征：由两段同种字符构成的字符串组成。比如，\(\texttt{aabb}\) 和 \(\texttt{ba}\) 就是这类子串，而 \(\texttt{aba}\) 或 \(\texttt{abc}\) 则不是。
而这种子串的数量，就是我们要的答案。
那么根据这种子串的特征，它又可以分成两段同种字符构成的字符串。所以，我们只需要算出由同种字符构成的子串数量 \(cnt\)，次数 \(ans=\lceil\dfrac{cnt}{2}\rceil\)
Part 2 代码
根据上方分析，可以写出计算次数函数：
int calc(string s){
int cnt=1;
for(int i=1;i<s.length();i++)
if(s[i-1]!=s[i])
cnt++;
return cnt/2+cnt%2; // 这里等同于 ceil(cnt/2.0)
}
结合其他部分，写出完整代码：
#include<iostream>
#define reg register
using namespace std;
int q;
string s;
int p;
char c;
inline int calc(string s){
reg int cnt=1;
for(reg int i=1;i<s.length();i++)
if(s[i-1]!=s[i])
cnt++;
return cnt/2+cnt%2;
}
int main(){
ios::sync_with_stdio(0);
cin>>q>>s;
cout<<calc(s)<<endl;
while(q--){
cin>>p>>c;
s[p-1]=c;
cout<<calc(s)<<endl;
}
return 0;
}
但是，如果你把这段代码提交上去，你只能得到 50 分。为什么？
因为这段代码的时间复杂度高达 \(O(\vert S\vert\cdot q)\)，你只能通过前 3 个 Subtask。
Part 3 优化
仔细观察上一段代码你就会发现它做了很多没用的事情。
在修改字符串时，子串数量 \(cnt\) 只与 \(s_{p-1}\)，\(s_p\)，\(s_{p+1}\) 和 \(c\) 有关。所以我们在每次修改后只需要维护上一次的 \(cnt\) 即可。
这里的维护代码：
cnt=cnt-((int)(s[p-2]!=s[p-1])+(int)(s[p-1]!=s[p]))+((int)(s[p-2]!=c)+(int)(c!=s[p]));
原理就是将原来函数内的循环展开，这里不过多解释，请自行思考。也可以修改函数使它支持单点维护但是我懒得写。
最终代码：
#include<iostream>
#define reg register
using namespace std;
int q;
string s;
int p;
char c;
int count(string s){
reg int cnt=1;
for(reg int i=1;i<s.length();i++)
if(s[i-1]!=s[i])
cnt++;
return cnt;
}
int main(){
ios::sync_with_stdio(0);
cin>>q>>s;
reg int cnt=count(s);
cout<<cnt/2+cnt%2<<endl;
while(q--){
cin>>p>>c;
cnt=cnt-((int)(s[p-2]!=s[p-1])+(int)(s[p-1]!=s[p]))+((int)(s[p-2]!=c)+(int)(c!=s[p]));
s[p-1]=c;
cout<<cnt/2+cnt%2<<endl;
}
return 0;
}