题解：B4426 [CSP-X2025 山东] IOI 串

题目大意

每次改变一个字符，要求我们求出最小操作次数，使得原字符串按顺序由连续个 I，连续个 O，连续个 I 组成。

题目解析

其实说白了，就是两个连续的 I 串中间夹了个 O 串。因为数据只有

n \le 5\times 10^3

，

n^2

为

10^7

级别刚好能过，我们可以考虑直接枚举 O 串的两个端点，对每种方案计算需要修改的字符数量，求最小值即可。

问题来了，怎么在

O(1)

的时间复杂度下计算要修改多少字符呢？因为我们枚举 O 串的两个端点，等于知道了 O 串的范围，进而可以知道在这个范围内 O 的数量，由此还可以推出前面的 I 的数量和后面 I 的数量，所以我们可以记录原字符串的字符在各个位置的数量，以此推导需要修改的字符量，而实现这个操作的最好方法就是前缀和。由于只有两种字符，因此我们记录一个前缀数组即可，另一个可以根据总数推出来。

如下图：（手稿图，将就看一下）

sum

记录第

i

个位置 O 的数量。图中是一个枚举范围到

i=6

，

j=13

时的情况。

红线和蓝线是要修改成 I 串的范围，绿线是 O 串范围。根据记录的

sum

和每个部分的长度，计算总共的修改次数。枚举完后取最小值即可。

一些坑点都在注释，详细请看代码：

AC code

CPP

#include <bits/stdc++.h>
using namespace std;
string s;
int sumo[5005];//O的前缀和
int main(){
	cin >> s;
	int ans=INT_MAX,len=s.size();
	for(int i=0;i<len;i++){
		if(i>0) sumo[i]=sumo[i-1];
		if(s[i]=='O') sumo[i]++;
	}
	for(int i=1;i<len-1;i++){//注意枚举i,j的范围不能包括头和尾，前后至少有一个I。
		for(int j=i;j<len-1;j++){
			ans=min(ans,sumo[i-1]+(j-i+1-(sumo[j]-sumo[i-1]))+(sumo[len-1]-sumo[j]));
//sumo[i-1]表示O串前面的I串中有几个O，即要修改几次。
//sumo[j]-sumo[i-1]表示O串中O的数量，j-i+1是O串的长度，即应该有几个O，两者的差就是修改次数。
//sumo[len-1]-sum[j]表示后面I串中O的数量
		}
	}
	cout << ans;
	return 0;
}

AC记录

题解：B4426 [CSP-X2025 山东] IOI 串

文章操作

题目大意

题目解析

AC code

相关推荐

评论

题解：B4426 [CSP-X2025 山东] IOI 串