基因锁

基因锁基因锁 时间限制 1 Sec 内存限制 128 MB 题目描述 小 终于意识到需要花大力气减重了 他询问了若干个减重专家后决定采用最适合年轻人的运动减重方案 考虑再三 小 最终选择了打羽毛球的方式 一个原因是小 的小伙伴大都喜欢打羽毛球

大家好,我是讯享网,很高兴认识大家。

基因锁

时间限制: 1 Sec  内存限制: 128 MB

题目描述

小X终于意识到需要花大力气减重了,他询问了若干个减重专家后决定采用最适合年轻人的运动减重方案,考虑再三,小X最终选择了打羽毛球的方式,一个原因是小X的小伙伴大都喜欢打羽毛球,其次是打羽毛球要抬头,对活动颈椎有好处,刚好可以缓冲编程久了对颈椎的压迫。
经过一个月的努力,小X的国际象棋 AI 在机器学习的环境中进步神速,已经能够轻松战胜深蓝了,但小X的体重却没有太大变化,离第一目标 Q 老师尚有一段距离,这天小X跟往常一样白天打羽毛球,晚上训练 AI 后就睡觉了,睡梦中小X梦见自己先是被一束强光罩住了,随后被吸进了 UFO,落到了 UFO 的甲板上,只见一只会说人话的机器狗迎上前来,对小X说:“小X先生好,我家主人在会客舱等你多时了!”
随后小X被带到了一位长了三只眼的外星首领面前。
外星首领很友善地和小X握了手,然后对小X说:“你做的 AI 非常棒,我已经很多年未遇对手了,今天跟你的 AI 打得旗鼓相当,十分过瘾,这次请你来作客是想和你交个朋友,你有什么要求尽管提,我们会尽量满足!”小X听罢受宠若惊,心想外星科技这么发达,也许有办法让我立刻变得像中天学长一样帅!
于是小X提出了这个超高难度的要求,外星首领听后微微一笑:“你这个要求可以满足,但我们要对你的基因进行一次分析,把你基因中的肥胖基因找出来,然后给它们加上锁!象我们熟知的那样,人类的基因序列(英文缩写为 DNA)是一个由字母'A','C','G','T'组成的字符串,肥胖基因是其中的一个子串(子串为原串中一段连续的字符),外星人对小X的基因手术过程是这样的:先找出所有的肥胖基因,并将它们用基因墨水染成红色,然后将某些字符加上基因锁,一把基因锁只能锁住一个字符,一个肥胖基因只要有一个字符加上了基因锁,则这个肥胖基因就不再起作用,现在要你计算有多少个字符被基因墨水染成了红色?最少需要多少把基因锁才能将所有的肥胖基因锁住?

 

输入

第一行包含两个用空格隔开的正整数 L1,L2,表示小X基因的长度和肥胖基因的长度。
第二行为一个长度为 L1 的字符串,表示小X的基因。
第三行为一个长度为 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'

暴力遍历一次就行了,复杂度最高为O(10n)。

用vis记录遍历过的且没有遇到重叠的,如果遇到重叠的,不需要锁,然后用vis1记录重叠之后的肥胖基因的部分,如果你还用vis记录,那么下次遇到重叠,如果那重叠的部分和前面的也重叠,但那重叠的部分没有配锁,答案就错了。

// #include <cstdio> #include <cstring> #include <cmath> #include <cctype> #include <iostream> #include <algorithm> #include <map> #include <set> #include <vector> #include <string> #include <stack> #include <queue> typedef long long LL; using namespace std; int vis[], vis1[]; int n, m, lens, lenstr; char s[], str[15]; int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); scanf("%d %d", &n, &m); scanf("%s %s", s, str); lens = strlen(s), lenstr = strlen(str); int ansnum = 0, ans = 0; for (int i = 0; i < lens; i++){ if(s[i] != str[0]) continue; int f = 0, t = i; for (int j = 0; j < lenstr; j++){ if(s[t++] != str[j]){ f = 1; break; } } if(!f){ int t = 0; for (int j = i; j < i + lenstr; j++){ if(vis[j]){ t = 1; for (; j < i + lenstr; j++) vis1[j] = 1; break; } vis[j] = 1; } if(!t) ans++; } } for (int i = 0; i < lens; i++){ if(vis[i] || vis1[i]) ansnum++; } printf("%d %d\n", ansnum, ans); return 0; } //

 

小讯
上一篇 2025-02-07 17:31
下一篇 2025-02-18 11:33

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/113126.html