自动搬运

查看原文

来自洛谷，原作者为

	AKPC 下次不写拍子我就是苟

搬运于2025-08-24 22:43:53，当前版本为作者最后更新于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;
}