首页 > 代码库 > 计蒜之道 初赛第一场B 阿里天池的新任务（简单）

计蒜之道 初赛第一场B 阿里天池的新任务（简单）

2024-09-23 19:37:40   206人阅读

阿里“天池”竞赛平台近日推出了一个新的挑战任务：对于给定的一串 DNA 碱基序列 tt，判断它在另一个根据规则生成的 DNA 碱基序列 ss 中出现了多少次。

首先，定义一个序列 ww：

 

\displaystyle w_{i} = \begin{cases}b, & i = 0\\(w_{i-1} + a) \mod n, & i > 0\end{cases}w?i??={?b,?(w?i−1??+a)modn,???i=0?i>0??

 

接下来，定义长度为 nn 的 DNA 碱基序列 ss（下标从 00 开始）：

 

\displaystyle s_{i} = \begin{cases}A , & (L \le w_{i} \le R) \land (w_{i}\ \mathrm{mod}\ 2 = 0)\\T , & (L \le w_{i} \le R) \land (w_{i}\ \mathrm{mod}\ 2 = 1)\\G , & ((w_{i} < L) \lor (w_{i} > R)) \land (w_{i}\ \mathrm{mod}\ 2 = 0)\\C , & ((w_{i} < L) \lor (w_{i} > R)) \land (w_{i}\ \mathrm{mod}\ 2 = 1)\end{cases}s?i??=?????????????????????A,?T,?G,?C,???(L≤w?i??≤R)∧(w?i?? mod 2=0)?(L≤w?i??≤R)∧(w?i?? mod 2=1)?((w?i??<L)∨(w?i??>R))∧(w?i?? mod 2=0)?((w?i??<L)∨(w?i??>R))∧(w?i?? mod 2=1)??

 

其中 \land∧ 表示“且”关系，\lor∨ 表示“或”关系，a\ \mathrm{mod}\ ba mod b 表示 aa 除以 bb 的余数。

现给定另一个 DNA 碱基序列 tt，以及生成 ss 的参数 n , a , b , L , Rn,a,b,L,R，求 tt 在 ss 中出现了多少次。

输入格式

数据第一行为 55 个整数，分别代表 n , a , b , L , Rn,a,b,L,R。第二行为一个仅包含A、T、G、C的一个序列 tt。

数据保证 0 < a < n,0<a<n, 0 \le b < n,0≤b<n, 0 \le L \le R < n,0≤L≤R<n, |t| \le 10^{6}∣t∣≤10?6??，a,na,n 互质。

对于简单版本，1 \leq n \leq 10^{6}1≤n≤10?6??；

对于中等版本，1 \leq n \leq 10^{9}, a = 11≤n≤10?9??,a=1；

对于困难版本，1 \leq n \leq 10^{9}1≤n≤10?9??。

输出格式

输出一个整数，为 tt 在 ss 中出现的次数。

样例说明

对于第一组样例，生成的 ss 为TTTCGGAAAGGCC。

样例输入1

13 2 5 4 9AGG

样例输出1

1

样例输入2

103 51 0 40 60ACTG

样例输出2

5
构造序列，然后就是裸的KMP，第一场就出线，好幸运哈哈哈哈哈哈
/** @Author: lyucheng* @Date:   2017-05-20 18:55:59* @Last Modified by:   lyucheng* @Last Modified time: 2017-05-20 20:43:25*/#include <bits/stdc++.h>#define LL long longusing namespace std;LL res=0;/*******************KMP模板***********************/void makeNext(const char P[],LL Next[]){    /*    Next[i]表示前i个字符中，最大前后缀相同的长度    */    LL q,k;    LL m=strlen(P);    Next[0]=0;    for (q=1,k=0;q<m;++q)    {        while(k>0&&P[q]!=P[k])            k = Next[k-1];        /*        这里的while循环很不好理解！        就是用一个循环来求出前后缀最大公共长度；        首先比较P[q]和P[K]是否相等如果相等的话说明已经K的数值就是已匹配到的长的；        如果不相等的话，那么Next[k-1]与P[q]的长度，为什么呐？因为当前长度不合适        了，不能增长模板链，就缩小看看Next[k-1]        的长度能够不能和P[q]匹配，这么一直递归下去直到找到        */        if(P[q]==P[k])//如果当前位置也能匹配上，那么长度可以+1        {            k++;        }        Next[q]=k;    }}void kmp(const char T[],const char P[],LL Next[]){    LL n,m;    LL i,q;    n = strlen(T);    m = strlen(P);    makeNext(P,Next);    for (i=0,q=0;i<n;++i)    {        while(q>0&&P[q]!= T[i])            q = Next[q-1];        /*        这里的循环就是位移之后P的前几个字符能个T模板匹配        */        if(P[q]==T[i])        {            q++;        }        if(q==m)//如果能匹配的长度刚好是T的长度那么就是找到了一个能匹配成功的位置        {            res++;        }    }}/*******************KMP模板***********************/LL n,a,b,L,R;char t[1000005];//用来匹配的子串char p[100000005];LL Next[100000005];LL last,now;LL len=0;int main(){    // freopen("in.txt","r",stdin);    scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&L,&R);    scanf("%s",t);    for(int i=0;i<n;i++){        if(i==0){            now=b;            if(now>=L&&now<=R){                if(now%2==0){                    p[len++]=‘A‘;                }else{                    p[len++]=‘T‘;                }            }else{                if(now%2==0){                    p[len++]=‘G‘;                }else{                    p[len++]=‘C‘;                }            }        }else{            now=(last+a)%n;            if(now>=L&&now<=R){                if(now%2==0){                    p[len++]=‘A‘;                }else{                    p[len++]=‘T‘;                }            }else{                if(now%2==0){                    p[len++]=‘G‘;                }else{                    p[len++]=‘C‘;                }            }        }        last=now;    }    makeNext(t,Next);    kmp(p,t,Next);    printf("%lld\n",res);    return 0;}

 

计蒜之道 初赛第一场B 阿里天池的新任务（简单）


联系
我们