【题目描述】

小Ｘ终于意识到需要花大力气减重了，他询问了若干个减重专家后决定采用最适合年轻人的运动减重方案，考虑再三，小Ｘ最终选择了打羽毛球的方式，一个原因是小Ｘ的小伙伴大都喜欢打羽毛球，其次是打羽毛球要抬头，对活动颈椎有好处，刚好可以缓冲编程久了对颈椎的压迫。
经过一个月的努力，小Ｘ的国际象棋 AI 在机器学习的环境中进步神速，已经能够轻松战胜深蓝了，但小Ｘ的体重却没有太大变化，离第一目标 Q 老师尚有一段距离，这天小Ｘ跟往常一样白天打羽毛球，晚上训练 AI 后就睡觉了，睡梦中小Ｘ梦见自己先是被一束强光罩住了，随后被吸进了 UFO，落到了 UFO 的甲板上，只见一只会说人话的机器狗迎上前来，对小Ｘ说：“小Ｘ先生好，我家主人在会客舱等你多时了！”
随后小Ｘ被带到了一位长了三只眼的外星首领面前。
外星首领很友善地和小Ｘ握了手，然后对小Ｘ说：“你做的 AI 非常棒，我已经很多年未遇对手了，今天跟你的 AI 打得旗鼓相当，十分过瘾，这次请你来作客是想和你交个朋友，你有什么要求尽管提，我们会尽量满足！”小Ｘ听罢受宠若惊，心想外星科技这么发达，也许有办法让我立刻变得像中天学长一样帅！

于是小Ｘ提出了这个超高难度的要求，外星首领听后微微一笑：“你这个要求可以满足，但我们要对你的基因进行一次分析，把你基因中的肥胖基因找出来，然后给它们加上锁！象我们熟知的那样，人类的基因序列(英文缩写为 DNA)是一个由字母’A’,‘C’,‘G’,'T’组成的字符串，肥胖基因是其中的一个子串(子串为原串中一段连续的字符)，外星人对小Ｘ的基因手术过程是这样的：先找出所有的肥胖基因，并将它们用基因墨水染成红色，然后将某些字符加上基因锁，一把基因锁只能锁住一个字符，一个肥胖基因只要有一个字符加上了基因锁，则这个肥胖基因就不再起作用，现在要你计算有多少个字符被基因墨水染成了红色？最少需要多少把基因锁才能将所有的肥胖基因锁住？

【输入描述】

第一行包含两个用空格隔开的正整数 L1，L2，表示小Ｘ基因的长度和肥胖基因的长度。
第二行为一个长度为 L1 的字符串，表示小Ｘ的基因。
第三行为一个长度为 L2 的字符串，表示肥胖基因。数据保证 L1>L2。

【输出描述】

【样例输入】

16 3
CGCGCATCGCATTAGG
CGC

【样例输出】

8 2

【题目分析】

主要解决两个问题：

一是找出所有肥胖基因在小Ｘ基因序列中出现的位置，并计算被染成红色（即属于肥胖基因的字符）的字符个数；

二是计算最少需要多少把基因锁，使得每个肥胖基因至少有一个字符被锁住。

具体步骤

1. 输入处理：读取小Ｘ基因的长度 L1、肥胖基因的长度 L2，以及小Ｘ的基因序列和肥胖基因序列。

2. 查找肥胖基因：在小Ｘ的基因序列中找出所有肥胖基因的出现位置。

3. 计算红色字符个数：统计所有肥胖基因覆盖的字符个数，注意避免重复计算。

4. 计算最少基因锁数量：通过贪心算法，选择合适的字符加锁，使得用最少的锁锁住所有肥胖基因。

【参考答案】

#include <iostream> 
using namespace std; 
 
const int MAX_LEN = 10000; 
 
int main() { 
    int L1, L2; 
    char gene[MAX_LEN], fatGene[MAX_LEN]; 
    bool isRed[MAX_LEN] = {false};  // 标记字符是否被染成红色 
    bool isLocked[MAX_LEN] = {false};  // 标记字符是否被加锁 
 
    // 输入小Ｘ基因的长度和肥胖基因的长度 
    cin >> L1 >> L2; 
 
    // 输入小Ｘ的基因序列 
    for (int i = 0; i < L1; i++) { 
        cin >> gene[i]; 
    } 
 
    // 输入肥胖基因序列 
    for (int i = 0; i < L2; i++) { 
        cin >> fatGene[i]; 
    } 
 
    // 查找肥胖基因并标记红色字符 
    for (int i = 0; i <= L1 - L2; i++) { 
        bool match = true; 
        for (int j = 0; j < L2; j++) { 
            if (gene[i + j] != fatGene[j]) { 
                match = false; 
                break; 
            } 
        } 
        if (match) { 
            for (int j = 0; j < L2; j++) { 
                isRed[i + j] = true; 
            } 
        } 
    } 
 
    // 计算红色字符个数 
    int redCount = 0; 
    for (int i = 0; i < L1; i++) { 
        if (isRed[i]) { 
            redCount++; 
        } 
    } 
 
    // 计算最少基因锁数量 
    int lockCount = 0; 
    for (int i = 0; i <= L1 - L2; i++) { 
        bool match = true; 
        for (int j = 0; j < L2; j++) { 
            if (gene[i + j] != fatGene[j]) { 
                match = false; 
                break; 
            } 
        } 
        if (match) { 
            bool isCovered = false; 
            for (int j = 0; j < L2; j++) { 
                if (isLocked[i + j]) { 
                    isCovered = true; 
                    break; 
                } 
            } 
            if (!isCovered) { 
                // 选择最后一个字符加锁 
                isLocked[i + L2 - 1] = true; 
                lockCount++; 
            } 
        } 
    } 
 
    // 输出结果 
    cout << redCount << " " << lockCount << endl; 
 
    return 0; 
}

代码解释

输入部分：使用 cin 读取小Ｘ基因的长度 L1、肥胖基因的长度 L2，以及小Ｘ的基因序列和肥胖基因序列。

查找肥胖基因：通过两层循环遍历小Ｘ的基因序列，检查每个长度为 L2 的子串是否与肥胖基因匹配。如果匹配，则将该子串中的所有字符标记为红色。

计算红色字符个数：遍历 isRed 数组，统计标记为红色的字符个数。

计算最少基因锁数量：再次遍历小Ｘ的基因序列，查找肥胖基因。对于每个未被加锁覆盖的肥胖基因，选择其最后一个字符加锁，以确保用最少的锁锁住所有肥胖基因。

输出结果：将红色字符个数和最少基因锁数量输出，中间用一个空格隔开