P8932

liucr · 2023-01-08 21:21:48 · 题解

在正解前先考虑暴力。

我们不难发现，可以将字符串分为每个字符都相等的一些子串。先要算出子串的个数。从下标为 1 的开始，枚举每个字符，如果后一个可以写出如下函数：

int query(){
    int ans=0;
    for (int i=1;i<(int)s.length();i++) if (s[i]!=s[i-1]) ans++;
    return ans;    //子串个数是ans+1
}

而我们可以在相邻子串的中间再插入这两个子串。如此反复下去可以达到要求。不难发现，答案就是 \lceil \dfrac{ans+1}{2} \rceil。

暴力代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
string s;
int query(){
    char ch=s[0];
    int ans=0;
    for (int i=1;i<(int)s.length();i++) if (s[i]!=ch) ans++,ch=s[i];
    return ans%2==1?(ans+1)/2:(ans+2)/2;    //等价于return ceil(ans+1);
}
int q,x;
char ch;
signed main(){
    cin>>q>>s;
    cout<<query()<<endl;
    while (q--){
        cin>>x>>ch;
        s[x-1]=ch;
        cout<<query()<<endl;
    }
    return 0;
}

但是这样的时间复杂度并不能通过本题。我们发现很多次枚举都重复了，没用处。其实我们只要对修改的部分进行枚举即可。

正解如下：

#include<bits/stdc++.h>
using namespace std;
string s;
int query(int l,int r){
    int ans=0;
    for (int i=l;i<=r;i++) if (s[i]!=s[i-1]) ans++;
    return ans;
}
int n,x,ans;
char ch;
int main(){
    cin>>n>>s;
    ans=query(1,(int)s.length()-1);
    ans%2==1?cout<<(ans+1)/2<<endl:cout<<(ans+2)/2<<endl;    //等价于cout<<ceil(ans+1)<<endl;
    while (n--){
        cin>>x>>ch;x--;
        ans-=query(x,x+1);
        s[x]=ch;
        ans+=query(x,x+1);
        ans%2==1?cout<<(ans+1)/2<<endl:cout<<(ans+2)/2<<endl;    //等价于cout<<ceil(ans+1)<<endl;
    }
    return 0;
}