P8932 [JRKSJ R7] Clock Paradox 题解

· · 题解

在博客园阅读 在洛谷博客阅读

Part 0 题意简述

原题这场月赛我唯一AC的题

给出一个字符串 S，令 T=S，求使用 S 的子串插入 T，将 T 变形的最少的操作次数。且字符串 S 会被修改 q 次。

具体变形：

~~看不懂？去看样例解释。~~ ## 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;
}