单词覆盖还原

洛谷·深入浅出 · 代码 · cpp · 难度 2/5 · 共 647 字

由覆盖后的字符串还原 boy 与 girl 的个数

洛谷
练习

正文

// 原题：https://oj.yecheng.tv/p/1423
// 题意：字符串由反复贴 boy/girl 得到，未被覆盖处用 '.' 表示。求实际贴了几个 boy、几个 girl。
// 思路：每个被贴的单词至少有 1 个字母保留在串上。对每个起点 i，若 s[i]='b' 或 s[i+1]='o' 或 s[i+2]='y'，
//       说明这里有一个 boy；girl 同理用 g/i/r 判断。
// 复杂度：O(n)。
// 易错点：靠“保留字母”来计数，不能直接数串里出现的字母；boy 与 girl 字母有重叠要分开判。
#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin >> s;
    int boy = 0, girl = 0;
    for(int i = 0; i + 2 < s.size(); i++){
        if(s[i] == 'b' || s[i + 1] == 'o' || s[i + 2] == 'y') boy++;
        if(s[i] == 'g' || s[i + 1] == 'i' || s[i + 2] == 'r') girl++;
    }
    cout << boy << endl << girl << endl;
    return 0;
}

单词覆盖还原

正文

洛谷·深入浅出的其它内容