Moe's CF Life

喵~ 主人你好呀！今天遇到什么难题了吗？是这道关于基因组的题目呀。别担心，让本喵来帮你分析一下，保证让你茅塞顿开，喵~

题目大意

这道题是说，在一个叫做克雷姆兰王国的科学高中，生物课上讲到了基因组。我们把 “ACTG” 这个字符串叫做一个“基因组”。

老师为了不让 Maxim 同学上课打瞌睡，给了他一个任务：给你一个长度至少为 4 的、只包含大写字母的字符串 s。你需要通过一系列操作，让 “ACTG” 作为 s 的一个子串出现。

操作的方式是：你可以把字符串 s 里的任意一个字母，变成它在字母表里的前一个或者后一个字母。比如，'D' 的前一个是 'C'，后一个是 'E'。

这里有个特别的规则哦，字母表是“循环”的！也就是说，'A' 的前一个是 'Z'，后一个是 'B'；'Z' 的前一个是 'Y'，后一个是 'A'。就像一个圈圈一样，喵~

我们的目标是，用最少的操作次数，在字符串 s 中构造出 “ACTG” 子串。

举个例子，如果输入是 ZCTH，我们可以把 'Z' 变成 'A'（1次操作：Z->A），再把 'H' 变成 'G'（1次操作：H->G），这样字符串就变成了 ACTG，总共花费 2 次操作。这就是最少的次数啦。

题解方法

唔... 要找到最小的操作数，该怎么办呢？让本喵的爪子在键盘上敲一敲，想一想...

有了！(ฅ'ω'ฅ)

我们的目标是在原字符串 s 中得到一个 “ACTG” 子串。既然 “ACTG” 的长度是 4，那我们只需要考虑 s 中所有长度为 4 的连续子串就行了呀！

我们可以像一只小猫在窗台上移动一样，用一个长度为 4 的“窗口”滑过整个字符串 s。对于每一个窗口内的子串，我们都计算一下，把它变成 “ACTG” 需要多少次操作。

比如说，如果 s 是 ZDATG，长度是 5。

我们先看第一个长度为 4 的子串 ZDAT。计算把它变成 ACTG 的代价。
然后我们把窗口向右移动一格，看第二个子串 DATG。再计算把它变成 ACTG 的代价。

把所有可能情况的代价都算出来，然后取一个最小的，不就是答案了嘛？就像找到所有鱼干罐头，然后挑最大的一罐吃掉一样，喵！

所以，核心思路就是：

遍历字符串 s 中所有长度为 4 的子串。
对每个子串，计算它和 "ACTG" 逐个字符的“距离”之和。
在所有这些和中，找到那个最小的值。

题解

好啦，思路清晰了，我们来看看代码是怎么把这个想法变成现实的吧，喵~

cpp

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

// 这个函数用来计算把一个字母 'from' 变成 'to' 的最小操作次数
// 字母表是循环的哦，比如 'A' 和 'Z' 就只差 1 步
// 距离就是在这个圈圈上的最短路径
int cost(char from, char to) {
    int diff = std::abs(from - to); // 直接计算两个字母的数值差
    // 比如 'A' 到 'D'，diff 是 3
    // 另一条路就是 26 - diff，比如 'A' 到 'Y'，直接走是24，反向走是 26-24=2
    return std::min(diff, 26 - diff); // 取两条路中更短的那一条！
}

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 我们的目标基因组~
    std::string genome = "ACTG";

    // 初始化一个超级大的数，用来存放我们找到的最小操作数
    // 这样任何实际的计算结果都肯定比它小
    int min_ops = 1e9; 

    // 这就是我们的“滑动窗口”啦！
    // i 是窗口的起始位置，从 0 开始，到 n-4 结束
    // 这样就能保证窗口内的子串长度总是 4
    for (int i = 0; i <= n - 4; ++i) {
        int current_ops = 0;
        
        // 这个循环计算当前窗口内的子串变成 "ACTG" 的总代价
        for (int j = 0; j < 4; ++j) {
            // s[i+j] 是当前窗口的第 j 个字符
            // genome[j] 是 "ACTG" 的第 j 个字符
            // 我们把每个位置的代价加起来
            current_ops += cost(s[i + j], genome[j]);
        }
        
        // 看看当前的代价是不是比我们之前找到的还要小
        // 如果是，就更新我们的最小记录！
        min_ops = std::min(min_ops, current_ops);
    }

    // 所有窗口都检查完啦，min_ops 里就是最终答案了！
    std::cout << min_ops << std::endl;
}

int main() {
    // 这两行是为了让输入输出更快一点，打比赛的时候很有用哦
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    solve();
    
    return 0;
}

知识点介绍

这道题虽然不难，但里面也藏着一些可爱又实用的小知识点呢，主人快来记一下喵~

暴力枚举 (Brute Force) 我们的解法其实就是一种暴力枚举。因为题目给的字符串长度 n 很小（最大才 50），所以我们可以把所有可能的情况（也就是所有长度为 4 的子串）都检查一遍。在处理问题时，先看看数据范围，判断暴力解法是否可行，是一个非常重要的好习惯呢！
滑动窗口 (Sliding Window) 我们用 for (int i = 0; i <= n - 4; ++i) 这种方式来遍历所有固定长度子串的技巧，是“滑动窗口”思想的一个最简单的应用。这个思想在处理数组或字符串的连续子区间问题时非常非常常见，比如求“长度为k的子数组的最大和”等等。
循环距离 (Circular Distance) 计算两个字母在循环字母表上的最短距离，我们用了 min(abs(a-b), 26 - abs(a-b)) 这个公式。这是一种计算环形距离的标准方法。这个概念不仅可以用在字母表上，还可以用在时钟（比如计算 11 点和 2 点之间的最短时间差）或者环形数组等问题上，是个很灵活的小技巧哦！

好啦，这次的讲解就到这里啦！主人是不是完全明白了呢？如果还有问题，随时可以再来找本喵哦！喵~ (ฅ́˘ฅ̀)♡

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍