您现在的位置是：主页 > news > 宁波住房和建设局网站/营业推广案例

宁波住房和建设局网站/营业推广案例

admin2025/4/21 12:57:28【news】

简介宁波住房和建设局网站,营业推广案例,团购的网站扣佣金分录怎么做,wordpress后台隐藏阿里天池的新任务（简单） 阿里“天池”竞赛平台近日推出了一个新的挑战任务：对于给定的一串 DNA 碱基序列 tt，判断它在另一个根据规则生成的 DNA 碱基序列 ss 中出现了多少次。首先，定义一个序列 ww： \dis…

宁波住房和建设局网站,营业推广案例,团购的网站扣佣金分录怎么做,wordpress后台隐藏阿里天池的新任务（简单） 阿里“天池”竞赛平台近日推出了一个新的挑战任务：对于给定的一串 DNA 碱基序列 tt，判断它在另一个根据规则生成的 DNA 碱基序列 ss 中出现了多少次。首先，定义一个序列 ww： \dis…

阿里天池的新任务（简单）

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

首先，定义一个序列 $w$ ：

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

接下来，定义长度为 $n$ 的 DNA 碱基序列 $s$ （下标从 $0$ 开始）：

$\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}$

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

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

输入格式

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

数据保证 $0 < a < n,$ $\le b < n,$ $\le L \le R < n,$ $\le 10^{6}$ ， $a, n$ 互质。

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

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

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

输出格式

输出一个整数，为 $t$ 在 $s$ 中出现的次数。

样例说明

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

样例输入1

13 2 5 4 9
AGG

样例输出1

样例输入2

103 51 0 40 60
ACTG

样例输出2

题目大意：中文题，不解释

解题思路：按要求生成文本串，用kmp模板求匹配数。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int MAXN=1e6+100;
LL ans;
int fail[MAXN];
LL n,a,b,L,R;
char ch[MAXN];char change(int i)
{LL wi=(b+i*a)%n;if(wi>=L&&wi<=R){if(wi%2==0) return 'A';else return 'T';}else{if(wi%2==0) return 'G';else return 'C';}
}void getfail(char *p)
{int plen=strlen(p);fail[0]=0,fail[1]=0;//递推初值for(int i=1;i<plen;i++){int j=fail[i];while(j&&p[i]!=p[j])j=fail[j];if(p[i]==p[j])fail[i+1]=j+1;elsefail[i+1]=0;}
}void kmp(char *p)
{int slen=n;int plen=strlen(p);int j=0;//当前结点编号for(int i=0;i<slen;i++)//文本串当前指针{while(j&&p[j]!=change(i))//顺着失配边走，直到可以匹配j=fail[j];if(p[j]==change(i))j++;if(j==plen){ans++;//cout<<"find at position "<<i-plen+1<<endl;j=fail[j];}}
}int main()
{while(scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&L,&R)!=EOF){scanf("%s",ch);ans=0;getfail(ch);
//        for(int i=0;i<=strlen(ch);i++)
//        {
//            cout<<fail[i]<<" ";
//        }
//        cout<<endl;kmp(ch);printf("%lld\n",ans);}return 0;