题目分析
给出一个字符串 \(s\)，允许改变 \(0\) 或 \(1\) 个字符，求其中 VK 的出现次数。
变量/数组/函数解析
int n 字符串 \(s\) 的长度
string s 字符串 \(s\)
int count(string s,string key) 自定义函数：求字符串 \(s\) 中 \(key\) 字符串的出现次数
int ans 答案记录器
思路
1.输入 \(n\) 和 \(s\)
cin>>n>>s;
2.for 循环模拟每次改变（时间复杂度\(\text{O}(n^2)\)，不会超时）
for(int i=0;i<len;i++){ //遍历
//替换
if(s[i]=='V'){
s[i]='K';
}
else{
s[i]='V';
}
//选取最大值
ans=max(ans,count(s,"VK"));
//回溯（还原回原字符串）
if(s[i]=='V'){
s[i]='K';
}
else{
s[i]='V';
}
}
函数体：
int count(string s,string key){
int cnt=0; //计数器
for(int i=0;i<=s.size()-key.size();i++){ //只遍历到前key.size()个
string k=s.substr(i,key.size()); //截取key.size()个字符
if(k==key){ //判断是否相符
cnt++; //计数器自增
}
}
return cnt; //返回计数器
}
3.输出答案
cout<<ans;
至此，这道题就做完了。完整代码看下面。
\(\text{AC Code}\)
#include<bits/stdc++.h>
using namespace std;
int count(string s,string key){
int cnt=0;
for(int i=0;i<=s.size()-key.size();i++){
string k=s.substr(i,key.size());
if(k==key){
cnt++;
}
}
return cnt;
}
int main(){
int len,ans=0;
string s;
cin>>len>>s;
if(len<2){
cout<<0;
return 0;
}
ans=count(s,"VK");
for(int i=0;i<len;i++){
if(s[i]=='V'){
s[i]='K';
}
else{
s[i]='V';
}
ans=max(ans,count(s,"VK"));
if(s[i]=='V'){
s[i]='K';
}
else{
s[i]='V';
}
}
cout<<ans;
return 0;
}