专栏文章

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

MMax_robot
B4426题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mincdil2
此快照首次捕获于
2025/12/02 00:06
3 个月前
此快照最后确认于
2025/12/02 00:06
3 个月前
查看原文

前言

这道题考场做了两个小时，发一下题解。
其实是为了某润田发的。

题目

我们需要将一个只包含 II 和 OO 的字符串转换为"好串"。好串的定义是：可以被划分为三个非空部分，依次为：
连续若干个 II
连续若干个 OO
连续若干个 II
例如：IIIOOIIIIIIIOOIIII 和 IOIIOI 都是好串，而 OIOIOIOI 和 IIOIIO 都不是好串。
目标是通过最少的修改操作（将 II 改为 OO 或将 OO 改为 II）将给定字符串变为好串。
是不是改变方式很像异或？其实后面根本用不着异或。

解题思路

这道题一开始我是想的是造两条线，从两侧分别往中心扫，这两条线其实就是 II 和 OO 的两个分界线。这个和本篇题解的代码其实都差不多，只是比较难想，不如这篇题解的代码好像，好处理。
核心思想就是枚举两条分界线，这两条线就是 II 和 OO 的两个分界线，然后就会分成三段。如下图。
第一部分：[1,i][1, i]
第二部分：[i+1,j][i+1, j]
第三部分：[j+1,n][j+1, n]
我们把三个部分需要改多少遍记录下来并相加。然后求最小值。
那么，怎么实现呢？
我们先求出前缀和。
我们枚举 ss，如果为 II，则 IiI_i 加一，否则 OiO_i 加一。
然后我们把前面的继承过来就行了。
如果不太理解就看下代码。
CPP
n=s.size();
	for(int i=1;i<=n;i++){//这里从 1 到 n 循环，主要是为了后面好计算
    	if(s[i-1]=='I'){//s 是从 0 到 size-1,所以这里是 s[i-1]
        	I[i]=I[i-1]+1;//将前面的继承并加 1
       	 	O[i]=O[i-1];//直接继承
  		}else{
        	I[i]=I[i-1];//直接继承
        	O[i]=O[i-1]+1;//继承并加一
    	}
	}
然后我们再想每一个部分应该怎么计算。
前缀和公式为 sr−sl−1s_r-s_{l-1}。
那么是不是知道范围就好了？
不过，先等等。
第一部分都是 II，所以第一部分的答案就是第一部分有多少 OO。
第二部分都是 OO，所以第二部分的答案就是第二部分有多少 II。
第三部分都是 II，所以第三部分的答案就是第三部分有多少 OO。
现在，是不是就可以求了？
第一部分：[1,i][1, i]
第二部分：[i+1,j][i+1, j]
第三部分：[j+1,n][j+1, n]
那么，第一部分就是 Oi−O1−1O_i-O_{1-1}，化简就是OiO_i。
第二部分就是 Ij−Ii+1−1I_j-I_{i+1-1}，化简就是Ij−IiI_j-I_i。
第三部分就是 On−Oj+1−1O_n-O_{j+1-1}，化简就是 On−OjO_n-O_j。
整理一下。
第一部分 Ij−IiI_j-I_i。
第二部分 Ij−IiI_j-I_i。
第三部分 On−OjO_n-O_j。
讲的已经很详细了，发一下代码。
CPP
ans=1e18;
	for(int i=1;i<n-1;i++){
		//这里就是i<=n-2,因为至少要留给 O 和 I 各一个位置,总共两个
        for(int j=i+1;j<n;j++){//从 i+1 开始,最后给 I 留一个位置
			/*
			now=0;
			now+=O[i]
			就等价于
			now=O[i]
			*/
            now=O[i];
            now+=I[j]-I[i];
            now+=O[n]-O[j];
            ans=min(ans,now);//取最小值
        }
    }
讲完了，思路已经出来了，把代码拼一下就好了。这里为了那些还是不懂的人发一下代码。

Code

CPP
#include<bits/stdc++.h>//万能头文件
using namespace std;
const int N=1e7+10;
string s;
long long n;
long long I[N], O[N];
long long now, ans;
int main(){
    cin>>s;//输入
	n=s.size();
	for(int i=1;i<=n;i++){//这里从 1 到 n 循环，主要是为了后面好计算
    	if(s[i-1]=='I'){//s 是从 0 到 size-1,所以这里是 s[i-1]
        	I[i]=I[i-1]+1;//将前面的继承并加 1
       	 	O[i]=O[i-1];//直接继承
  		}else{
        	I[i]=I[i-1];//直接继承
        	O[i]=O[i-1]+1;//继承并加一
    	}
	}
	ans=1e18;//ans 初值inf
	for(int i=1;i<n-1;i++){
		//这里就是i<=n-2,因为至少要留给 O 和 I 各一个位置,总共两个
        for(int j=i+1;j<n;j++){//从 i+1 开始,最后给 I 留一个位置
			/*
			now=0;
			now+=O[i]
			就等价于
			now=O[i]
			*/
            now=O[i];
            now+=I[j]-I[i];
            now+=O[n]-O[j];
            ans=min(ans,now);//取最小值
        }
    }
	cout<<ans<<endl;//输出答案
	return 0;//完结撒花
}

算法分析

时间复杂度

前缀和预处理：O(n)O(n)。
双重循环枚举分界点：O(n2)O(n^2)。
总时间复杂度：O(n2)O(n^2)。
对于 n≤5000n \leq 5000 的数据范围，O(n2)O(n^2) 算法是可行的。
其实这道题是可以 O(n)O(n) 的，不过对于大部分考 XX 的人来说可能很难，所以不讲解。大家可以试一试。

完结撒花

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...