上海计算机学会2023年12月月赛C++丙组T5特定的串
发布时间
阅读量：
阅读量
特定的串
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定一个 01 序列 b1b2…bn，01 的意思就是这个数列里只有 0 与 1。
我们可以修改该序列的任意一个数字，可以将 0 变成 1，也可以将 1 变成 0，注意不能删除或增加数字。
请问，最少需要修改多少数字才能让给定的序列中不含有特定的一个子串 110。
输入格式
- 第一行：单个整数 n。
- 第二行：n 个字符表示 b1b2…bn，保证只出现
0与1。
输出格式
- 单个整数表示答案
数据范围
- 对于 30% 的数据，1≤n≤20；
- 对于 60% 的数据，1≤n≤2000；
- 对于 100% 的数据，1≤n≤500,000
样例数据
输入:
4
1101
输出:
1
说明:
改0为1
输入:
5
11000
输出:
1
说明:
该第二个1为0
解析：
想要消灭110串，两种办法：
一是把所有0改成1；
二是把所有11改成10；
取最小值，可以得90分
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int ans1=0;//把0都变成1
int ans2=0;//把11变成10
int main() {
cin >> n;
int num=0;//统计连续1的个数
for (int i=1;i<=n;i++){
char ch;
cin>>ch;
if (ch=='0'){
ans1++;
ans2+=num/2;
num=0;
}else{
num++;
}
}
cout<<min(ans1,ans2);
return 0;
}
正解：
以所有的01为分界线，可以把前边所有的11改成10，把后边所有的0改成1，取最小值。
详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int ans2=0;//把11变成10
int a[500005];//a[i]表示从i位置开始到结尾一共多少个0
string s;
int ans=1e9;
int main() {
cin>>n;
cin>>s;
s+='0';
for(int i=n-1;i>=0;i--){
if (s[i]=='0'){
a[i]=a[i+1]+1;
}else{
a[i]=a[i+1];
}
}
int num=0;//统计连续1的个数
for (int i=0;i<=n;i++){
if (s[i]=='0'){
ans=min(ans,ans2+a[i]);
ans2+=num/2;
num=0;
}else{
num++;
}
}
cout<<ans;
return 0;
}
全部评论 (0)
还没有任何评论哟~