题解：P13894 [蓝桥杯 2023 省 C] 填充

· · 题解

题解：P13894 [蓝桥杯 2023 省 C] 填充

思路

很简单的贪心。

我们可以用一个循环把所有 str[i]==str[i-1] 的子串找出来。然后统计 ? 的个数，每遇到一次 ? 就让他和上一位相等即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
string str;
int ans=0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>str;
    for(int i=1;i<str.size();i++){
        if(str[i]==str[i-1]){
            ans++;
            i++;
        }else if(str[i]=='?'){
            ans++;
            i++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

结果炸了……

为什么呢？

因为还有一种情况：

 被遗忘了
    |
    V
1 ? ? 0 0
  |   ^
  |---|
  V 到这一位
 跳过

所以我们还需要统计 str[i-1]=='?' 的情况。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
string str;
int ans=0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>str;
    for(int i=1;i<str.size();i++){
        if(str[i]==str[i-1]){
            ans++;
            i++;
        }else if(str[i]=='?'){
            ans++;
            i++;
        }else if(str[i-1]=='?'){
            ans++;
            i++;
        }
    }
    cout<<ans<<endl;
    return 0;
}