在洛谷上阅读
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;
}
标签:子串,cnt,R7,Paradox,string,int,题解,texttt,reg
From: https://www.cnblogs.com/WorldHim/p/solution-luogu-p8932.html