B3891 [语言月赛 202311] 基因 题解

· · 题解

Source & Knowledge

2023 年 11 月语言月赛，由洛谷网校入门计划/基础计划提供。

考察字符串的运用。

文字题解

本题考察字符串的运用。首先，我们应该如何读取一个字符串呢？这里有多种方式：

对于字符串（string）类型的变量 s，以下都是可能的读入方式：

cin >> s;//读入一个字符串，读到空格或者换行截断
getline(cin,s);//读入一整行字符

对于字符数组类型的字符串 ch[]，以下都是可能的读入方式：

cin >> ch;//从 ch[0] 开始填充字符数组，每个字符占一位
scanf("%s",ch);//同上
cin >> (ch+1);//从 ch[1] 开始填充字符数组，在 C++20 以后被弃用。
fgets(ch,MAX_SIZE,stdin);//读入一行的字符填充入字符数组中，其中 MAX_SIZE 可以理解为一次性最多允许读入的字符量

而不推荐使用以下方式读入字符或者字符串：

char ch=getchar();//容易被各种平台下的换行符坑害
gets(s);//被弃用

假设我们现在使用了任何一种字符串的读入方式读入下了这个字符串，接下来我们应当如何处理翻转呢？

方法 1：使用 std::reverse() 函数。对于使用了字符串（string）而言，直接使用 reverse(s.begin(),s.end())，就可以翻转一条字符串 s 了（需要头文件：algorithm）。

方法 2：使用一个循环。具体而言，假设我们下标从 0 到 n 去存储一个字符串 s，那么其翻转后的字符串 s1 可以用这种方式获得：

for (int i=0;i<n;i++)
    s1[i]=s[n-i-1];

接着我们只需根据题意，找出字符串中不为 \tt A,\tt T,\tt C,\tt G 的那些字符，再让字符进行配对就可以了。

问题真的就这么结束了吗？并没有那么容易。这个题目最大的坑点在于稳定度最大能够是多少？很显然，我们可以构造出一个像 \tt{AAATTT} 的字符串，其每一位都能配对得上，贡献一次稳定度。也就是说，稳定度的最大值是：

1+2+3+\dots+n=\dfrac{n(n+1)}{2}

代入 n=100000 的上限，可知其大约是 5\times 10^9 的范围，恰好超过了 int 类型所能容纳的最大值（约 2.1\times 10^9），因此需要使用 long long 类型的变量存储该值。

详细的代码请参考视频题解。