正文
♦时间复杂度:\(\mathcal{O}(|S|+q)\)
找规律的题。
我们先来研究三组数据:
-
abcd
,答案是 2; -
aa
,答案是 1; -
ccffab
,答案是 2。
以下称将一个子串按题意每个字符双倍的操作为完成。
第一组数据,我们把子串 ab
、cd
插入原字符串即可得到 \(T\),由此我们可以得知:每两个不同字母可以一次完成。
第二组数据,我们把子串 aa
插入原字符串末即可得到 \(T\),由此,我们得知:多个连续相同字母可以一次完成。
第三组数据是第一组、第二组数据的综合,我们截取子串 ccff
、ab
即可,为了表达清楚,在这里先做一个定义:单个最长的由相同字母组成的子串称为一块(第三组数据的块有:cc
、ff
、a
、b
),然后我们就可以清晰地说明我们的发现:每两个块(或单个块)可以一次完成。第三组数据中有 4 个块,所以最快只要 \(4\div 2=2\) 次。
由上,我们设每个 \(S\) 由 \(m\) 个块组成,那么答案为 \(\left \lfloor m \div 2\right \rfloor + m\bmod 2\)。
那静态问题我们解决了,剩下的 \(q\) 次修改怎么办呢?
其实很好办的,比如我们将 aacd
的第 2 个字符修改成 c
,即将原字符串变成 accd
,我们可以研究一下这个字符串的块的变化:
我们设 \(a\) 为原始字符串的块数,原始字符串有 3 个块(\(a\leftarrow 3\)),修改后我们可以发现,第二个字符和它左边的字符不再构成同一个块,我们可以 \(a\leftarrow a-1\),即 C++ 中的 a--
。我们继续分析,第二个字符改成了 c
,和它右边的字符组成了一个块,我们可以 \(a\leftarrow a+1\),或者说 a++
。
设 \(x\) 为一个字符,\(S=\overline{x_1x_2x_3}\)。假设我们要修改 \(x_2\),我们可以总结出:若原来的 \(x_2\) 和左边的字符(\(x_1\))构成块,那么 \(a\leftarrow a-1\),右边的字符(\(x_3\))同理。然后,若修改后的 \(x_2\) 和左边的字符构成块,那么 \(a\leftarrow a+1\),右边也同理。
这样,每次修改操作我们就可以以 \(\mathcal{O}(1)\) 解决,每次输出 \(\left \lfloor a \div 2\right \rfloor + m\bmod 2\) 就行。
代码参上:
#include<iostream>
#include<string>
using namespace std;
int q,a,cnt;
char c;
string s;
int main(){
ios::sync_with_stdio(false),
cin.tie(nullptr);
cin>>q>>s;
int k=0,d=s.size();
s+="#";//方便后续操作,且能防止越界
while(k<d){//指针法,k为指针,判断一个块,cnt记录s有多少块
while(s[k+1]==s[k]) k++;
k++,cnt++;
}
cout<<cnt/2+cnt%2<<'\n';
s="#"+s;//方便后续操作,且能防止越界
while(q--){//判断相邻的字符是否构成块且更改cnt(当前字符串块数)
cin>>a>>c;
if(s[a]==s[a-1]) cnt++;
if(s[a]==s[a+1]) cnt++;
s[a]=c;
if(s[a]==s[a-1]) cnt--;
if(s[a]==s[a+1]) cnt--;
cout<<cnt/2+cnt%2<<'\n';
}
}
后附
日志
v1.0 on 2023.01.07: 发布
标签:子串,字符,cnt,洛谷,leftarrow,题解,P8932,字符串,我们 From: https://www.cnblogs.com/wanguan/p/17033529.html