2024-08-12 19:25:41 星期一
一言: Cannot get hitokoto.
下面这题好难啊
//网址:file:///C:/Users/Lenovo/Downloads/%E9%A2%98%E7%9B%AE.pdf
基因锁(e.cpp 或 e.pas)
问题描述
小Ｘ终于意识到需要花大力气减重了，他询问了若干个减重专家后决定采用最适合年轻人的运动减重方案，考虑再三，小Ｘ最终选择了打羽毛球的方式，一个原因是小Ｘ的小伙伴大都喜欢打羽毛球，其次是
打羽毛球要抬头，对活动颈椎有好处，刚好可以缓冲编程久了对颈椎的压迫。经过一个月的努力，小Ｘ的国际象棋 AI 在机器学习的环境中进步神速，已经能够轻松战胜深蓝了，但小Ｘ的体重却没有太大变化，离第一目标 Q 老师尚有一段距离，这天小Ｘ跟往常一样白天打羽毛球，晚上训练 AI 后就睡觉了，睡梦中小Ｘ梦见自己先是被一束强光罩住了，随后被吸进了UFO，落到了UFO的甲板上，只见一只会说人话的机器狗迎上前来，对小Ｘ说：“小Ｘ先生好，我家主人在会客舱等你多时了！”随后小Ｘ被带到了一位长了三只眼的外星首领面前。
外星首领很友善地和小Ｘ握了手，然后对小Ｘ说：“你做的 AI 非常棒，我已经很多年未遇对手了，今天跟你的 AI 打得旗鼓相当，十分过瘾，这次请你来作客是想和你交个朋友，你有什么要求尽管提，我们会尽量满足！”小Ｘ听罢受宠若惊，心想外星科技这么发达，也许有办法让我立刻变得像中天学长一样帅！于是小Ｘ提出了这个超高难度的要求，外星首领听后微微一笑：“你这个要求可以满足，但我们要对你的基因进行一次分析，把你基因中的肥胖基因找出来，然后给它们加上锁！象我们熟知的那样，人类的基因序列(英文缩写为 DNA)是一个由字母'A','C','G','T'组成的字符串，肥胖基因是其中的一个子串(子串为原串中一段连续的字符)，外星人对小Ｘ的基因手术过程是这样的：先找出所有的肥胖基因，并将它们用基因墨水染成红色，然后将某些字符加上基因锁，一把基因锁只能锁住一个字符，一个肥胖基因只要有一个字符加上了基因锁，则这个肥胖基因就不再起作用，现在要你计算有多少个字符被基因墨水染成了红色？最少需要多少把基因锁才能将所有的肥胖基因锁住？
输入格式
第一行包含两个用空格隔开的正整数 L1，L2，表示小Ｘ基因的长度和肥胖基因的长度。第二行为一个长度为 L1 的字符串，表示小Ｘ的基因。
第三行为一个长度为 L2 的字符串，表示肥胖基因。数据保证 L1>L2。
样例输入
16 3
CGCGCATCGCATTAGG
CGC
输出格式
输出一行包含两个整数，表示被基因墨水染成了红色的字符个数和所需的基因锁数量，两数之间严格用一个空格隔开。
样例输出
8 2
样例解释
红色字符为被基因墨水染成红色的全部 3 个肥胖基因，总共有 8 个字符；只需2 把基因锁就可以把所有的肥胖基因(CGC)锁住。分别锁住第 3 个字符‘C’和第 9 个字符‘G’即可。注意第一个和第二个肥胖基因有重叠，给第三个字符‘C’加上锁就同时将两个肥胖基因锁住了。
数据范围
10%的数据，肥胖基因为单个字符
40%的数据，所有的肥胖基因互相不重叠
100%的数据，基因长度不超过 10^6，肥胖基因长度不超过 10，保证字符只会出现'A','C','G','T'
这好像是上面那题的题解
#include
using namespace std;
int main(){
int l1,l2,x = 0,lastpos = -1,inklen = 0,lockpos = -1,genelock = 0;
string dna,fat;
cin >> l1 >> l2 >> dna >> fat;
while (dna.find(fat,x) != dna.npos){
x = dna.find(fat,x);
if (x > lockpos){
genelock++;
lockpos = x + fat.size() - 1;
}
if (lastpos < x) inklen += fat.size();
else inklen += x + fat.size() - 1 - lastpos;
lastpos = x + fat.size() - 1;
x++;
}
cout << inklen << " " << genelock << endl;
return 0;
}
以上就是我第一天写blog的全部内容了
Wishing me a better tomorrow！