题解：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 的数量，所以我们可以记录原字符串的字符在各个位置的数量，以此推导需要修改的字符量，而实现这个操作的最好方法就是前缀和。由于只有两种字符，因此我们记录一个前缀数组即可，另一个可以根据总数推出来。

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

![](https://cdn.luogu.com.cn/upload/image_hosting/0o3hgn1e.png) 红线和蓝线是要修改成 `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记录](https://www.luogu.com.cn/record/245990107)