T1：
一只青蛙失去了荷叶的保护。
它十分迷茫，于是决定改变自己的基因，让自己成为一个受庇护的不会老去的物种。众
所周知，青蛙的基因是一段有遗传效应 DNA 片段，我们认为这个片段仅由“A”，“ T”，
“C”，“ G”组成，为了方便，我们只需考虑DNA的一条链。
这只青蛙十分有经验，它知道这条链长度为 n，并且知道有庇护效应的序列有 m 种，
它希望使得这条链上的每一个位置都受到庇护。注意有庇护效应的序列可以相互重叠，一个
位置被庇护当且仅当它被至少一个有庇护效应的序列包含。
这只青蛙想要知道有多少种满足条件的链，对 109+9取模。
对于100％的数据1<=n<=1000，1<=m<=10 , 有庇护效应的序列长度不超过10
分析：
涉及到多个字符串匹配的问题，首先考虑AC自动机。
定义dp[i][j][k]为已凑出i的长度，在AC自动机的j号节点，从后往前数第k个位置还未被覆盖（且是最左的未被覆盖的）。
利用AC自动机跳fail预处理出每一个节点包含的最长庇护长度，转移的时候就判断覆盖的长度是否大于等于k+1（包括了k点），是就说明可以将k覆盖，转移到dp[i+1][son][0]（son是当前节点的儿子节点）
否则就转移到dp[i+1][son][k+1] k+1是因为多了这个节点没被覆盖。
#include<bits/stdc++.h>
using namespace std;
#define N 105
#define ri register int
const int mod=1e9+9;
int ndnum=0,ed[N],go[N][5],r[N],fail[N],dp[1005][N][12],n,m;
char s[15];
void add()
{
int len=strlen(s+1),now=0;
for(ri i=1;i<=len;++i){
int c=r[(int)s[i]];//printf("%d\n",c);
if(!go[now][c]) go[now][c]=++ndnum;
now=go[now][c];
}
ed[now]=len;
}
void get_fail()
{
queue<int> q;
for(ri i=0;i<=3;++i) if(go[0][i]) q.push(go[0][i]);
while(!q.empty()){
int now=q.front(); q.pop();//printf("now:%d\n",now);
for(ri i=0;i<=3;++i){
if(!go[now][i]) go[now][i]=go[fail[now]][i];
else{
fail[go[now][i]]=go[fail[now]][i];
q.push(go[now][i]);
ed[go[now][i]]=max(ed[go[now][i]],ed[fail[go[now][i]]]);
//通过求fail指针的同时 求出以这个点结尾的能覆盖的最长长度
}
}
}
}
void work()
{
dp[0][0][0]=1;
for(ri i=0;i<n;++i)
for(ri j=0;j<=ndnum;++j)//0是根节点
for(ri k=0;k<=9;++k){//9是因为要转移到k+1
if(!dp[i][j][k]) continue;
for(ri p=0;p<=3;++p){
int son=go[j][p];//遍历当前节点的每一个儿子
if(ed[son]>=k+1) dp[i+1][son][0]=(dp[i+1][son][0]+dp[i][j][k]) %mod;
//如果可以覆盖 就转移到只有倒数0位没有被覆盖 否则加上这一个就多了一个没有被覆盖的 转移到k+1
else dp[i+1][son][k+1]=(dp[i+1][son][k+1]+dp[i][j][k]) %mod;
}
}
int ans=0;
for(ri i=0;i<=ndnum;++i) ans=(ans+dp[n][i][0]) %mod;
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&m);
r[(int)'A']=0; r[(int)'C']=1; r[(int)'G']=2; r[(int)'T']=3;
for(ri i=1;i<=m;++i) scanf("%s",s+1),add();
get_fail();
work();
return 0;
}
/*
6 2
CAT
TACT
*/
View Code
T2：
在获得庇护的同时，这只青蛙(或者称为别的什么物种)还获得了一股强大的力量。它的
存在已经超出了自然世界的其他一切生物，于是它想要突破界限，掌握这股力量。
现在它得到了一本古老的书籍，并且将其翻译得到了一个长为 n 的由小写字母构成的
字符串，现在，它想要找到一个最长的子串，使得这个子串既是字符串的前缀又是后缀，并
且在字符串的中间出现过(即在非前后缀的位置出现过)。
由于剧情需要，我们保证存在这样一个满足条件的子串。
对于100％的数据，n<=10000000
分析：
考虑kmp中nex数组的定义：nex[i]=j表示1~j与i-j+1~i匹配，且j最大，也就是最长的前缀与后缀相同。
但这道题还有一个限制：必须在中间出现过。如果直接取nex[n]，并且中间有一个位置满足条件，那么一定会有nex[x]==nex[n]。
如果不存在这样的x，说明长度应该缩小，怎么缩呢，跳nex！！
原本长度为3，因为不满足中间出现过，所以通过跳n的nex来缩短长度，找到一个更短的，满足中间出现过的。
#include<bits/stdc++.h>
using namespace std;
#define ri register int
#define N 10000005
int nex[N],n;
char s[N];
bool vis[N];
void get_next()
{
nex[0]=nex[1]=0;
for(ri i=2,j=0;i<=n;++i){
while(j>0 && s[i]!=s[j+1]) j=nex[j];
if(s[i]==s[j+1]) j++;
nex[i]=j;
if(i!=n) vis[j]=true;
}
for(ri i=1;i<=n;++i)
printf("%d ",nex[i]);
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
get_next();
int now=n;
while(!vis[nex[now]] && now>0) now=nex[now];
printf("%d\n",nex[now]);
}
/*
abababadababa
*/
View Code
T3：
这只小动物找到了书中的力量，它几乎就要成功了，依据书中内容，它还缺一副眼镜。
于是它找到了一个 01 串，想要从中找到制造眼镜的材料。它希望找到这个 01 串的最
长的子序列串(即不要求连续)，这个子序列满足01交间的性质(01010…或10101…)。
但是在寻找之前，它想测试一下目前拥有的力量，于是它选择了一段连续的区间，将这
个区间中的0变成1、1变成0，再在其中寻找最长01交间子序列串。
当然，它希望合适地运用仅一次自己的力量(但一定要使用)，使得这个子序列串变得尽
可能长。
分析：
通过画图，出多组数据分析可知，无论怎么翻转，每次对答案最多贡献2，所以只需要求出初始01串长，然后再+2即可（注意和n取min）
#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define ri register int
char s[N];
int a[N],tmp[N],n;
int check(int l,int r)
{
memcpy(tmp,a,sizeof(a));
for(ri i=l;i<=r;++i) tmp[i]^=1;
int cnt1=0,cnt2=0,need=0;
for(ri i=1;i<=n;++i) if(tmp[i]==need) cnt1++,need^=1;
need=1;
for(ri i=1;i<=n;++i) if(tmp[i]==need) cnt2++,need^=1;
return max(cnt1,cnt2);
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
int ans=0;
for(ri i=1;i<=n;++i) a[i]=s[i]-'0';
printf("%d\n",min(check(0,0)+2,n));
}
/*
10000011
11000111100001010101
10010110011000001111
10101010101
*/
View Code