时间戳

首页 > 技术文章 > BZOJ 4212: 神牛的养成计划

BZOJ 4212: 神牛的养成计划

Oncle-Ha 2017-03-22 10:58 原文

4212: 神牛的养成计划

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 148  Solved: 33
[Submit][Status][Discuss]

Description

Hzwer成功培育出神牛细胞，可最终培育出的生物体却让他大失所望......
 
后来，他从某同校女神 牛处知道，原来他培育的细胞发生了基因突变，原先决定神牛特征的基因序列都被破坏了，神牛hzwer很生气，但他知道基因突变的低频性，说不定还有以下优秀基因没有突变，那么他就可以用限制性核酸内切酶把它们切出来，然后再构建基因表达载体什么的，后面你懂的......
 
黄学长现在知道了N个细胞的DNA序列，它们是若干个由小写字母组成的字符串。一个优秀的基因是两个字符串s1和s2,当且仅当s1是某序列的前缀的同时，s2是这个序列的后缀时，hzwer认为这个序列拥有这个优秀基因。
 
现在黄学长知道了M个优秀基因s1和s2，它们想知道对于给定的优秀基因，有多少个细胞的DNA序列拥有它。
 

 

Input

第一行：N，表示序列数
接下来N行，每行一个字符串，代表N个DNA序列，它们的总长为L1
接下来一个M，表示询问数
接下来M行，每行两个字符串s1和s2，由一个空格隔开，hzwer希望你能在线回答询问，所以s1等于“s1”的所有字符按字母表的顺序向后移动ans位（字母表是一个环），ans为上一个询问的答案，s2同理。例如ans=2  “s1”=qz
则s1=sb。对于第一个询问，ans=0
s1和s2的总长度为L2
 

 

Output

输出M行，每行一个数，第i行的数表示有多少个序列拥有第i个优秀基因。
 

Sample Input

10
emikuqihgokuhsywlmqemihhpgijkxdukjfmlqlwrpzgwrwozkmlixyxniutssasrriafu
emikuqihgokuookbqaaoyiorpfdetaeduogebnolonaoehthfaypbeiutssasrriafu
emikuqihgokuorocifwwymkcyqevdtglszfzgycbgnpomvlzppwrigowekufjwiiaxniutssasrriafu
emikuqihgokuorociysgfkzpgnotajcfjctjqgjeeiheqrepbpakmlixyxniutssasrriafu
emikuqihgokuorociysgfrhulymdxsqirjrfbngwszuyibuixyxniutssasrriafu
emikuqihgokuorguowwiozcgjetmyokqdrqxzigohiutssasrriafu
emikuqihgokuorociysgsczejjmlbwhandxqwknutzgdmxtiutssasrriafu
emikuqihgokuorociysgvzfcdxdiwdztolopdnboxfvqzfzxtpecxcbrklvtyxniutssasrriafu
emikuqihgokuorocsbtlyuosppxuzkjafbhsayenxsdmkmlixyxniutssasrriafu
emikuqihgokuorociysgfjvaikktsixmhaasbvnsvmkntgmoygfxypktjxjdkliixyxniutssasrriafu
10
emikuqihgokuorociysg yxniutssasrriafu
aiegqmedckgqknky eqpoowonnewbq
xfbdnjbazhdnhkhvb qrqgbnmlltlkkbtyn
bjfhrnfedlhrlolzfv qppxpoofxcr
zhdfpldcbjf stsidponnvnmmdvap
zhdfpldcbjfpjmjxdt gdstsidponnvnmmdvap
dlhjtphgfnjtnqnbhxr wxwmhtsrrzrqqhzet
bjfhrnfedlhrlolzfv frqppxpoofxcr
zhdfpldcbjf dponnvnmmdvap
ucyakgyxweakehes nondykjiiqihhyqvk

Sample Output

4
7
3
5
5
1
3
5
10
4

HINT

 

N<=2000

L1<=2000000

M<=100000

L2<=2000000

 

 

Solution

先将序列串正序插入trie树，S1匹配到trie树一个节点X，那S1为其子树所有节点表示串的前缀。X的子树满足S1为其前缀。每个节点记录其包含的序列尾节点区间。

然后用DFS序转换为区间，在区间上逆序插入可持久化trie树，来匹配S2的逆序。

trie树+可持久化trie树：

复杂度O(L1+L2)。

  1 #include<cstdio>
  2 #include<string>
  3 #include<vector>
  4 #include<cstring>
  5 const int len(2000),lem(2000000);
  6 struct Trie{int nx[26],tag;}trie[lem+10];
  7 int tot=1,tp,sz[len+10];std::vector<int>line[len+10];
  8 int Eu[lem+10],size[lem+10],cnt;
  9 struct CMTrie{int nx[26],sum;}tree[lem+10];
 10 int stot,root[len+10];
 11 int n,m,x,ans,leng[len+10],l1,l2;
 12 char tmp[lem+10],s1[lem+10],s2[lem+10];std::string D[len+10];
 13 void insert(int k,int x,int l)
 14 {
 15     if(l==leng[x])
 16     {
 17         if(!trie[k].tag)trie[k].tag=++tp;
 18         line[trie[k].tag].push_back(x);
 19         sz[trie[k].tag]++;
 20         return ;
 21     }
 22     int next=(D[x][l]-'a');
 23     if(!trie[k].nx[next])trie[k].nx[next]=++tot;
 24     insert(trie[k].nx[next],x,l+1);
 25 }
 26 int ins(int k,int x,int l)
 27 {
 28     if(!l)
 29     {
 30         tree[++stot]=tree[k];
 31         tree[stot].sum++;
 32         return stot;
 33     }
 34     int next=(D[x][l]-'a');
 35     int tmp=ins(tree[k].nx[next],x,l-1);
 36     tree[++stot]=tree[k];
 37     tree[stot].sum-=tree[tree[stot].nx[next]].sum;
 38     tree[stot].nx[next]=tmp;
 39     tree[stot].sum+=tree[tree[stot].nx[next]].sum;
 40     return stot;
 41 }
 42 void dfs(int k)
 43 {
 44     if(trie[k].tag)
 45     {
 46         Eu[k]=++cnt;root[cnt]=root[cnt-1];size[k]=1;
 47         for(int v=0;v<sz[trie[k].tag];v++)
 48             root[cnt]=ins(root[cnt],line[trie[k].tag][v],leng[line[trie[k].tag][v]]);
 49     }else Eu[k]=cnt+1;
 50     for(int v=0;v<26;v++)
 51     if(trie[k].nx[v])
 52     {
 53         dfs(trie[k].nx[v]);
 54         size[k]+=size[trie[k].nx[v]];
 55     }
 56 }
 57 int match(int k)
 58 {
 59     int l=0;
 60     for(;l<=l1;l++)
 61         k=trie[k].nx[s1[l]-'a'];
 62     return k;
 63 }
 64 int match(int k1,int k2)
 65 {
 66     int l=l2;
 67     for(;l>=0;l--)
 68     k1=tree[k1].nx[s2[l]-'a'],k2=tree[k2].nx[s2[l]-'a'];
 69     return tree[k1].sum-tree[k2].sum;
 70 }
 71 int main()
 72 {
 73 //    freopen("C.in","r",stdin);
 74 //    freopen("C.out","w",stdout);
 75     scanf("%d",&n);
 76     for(int i=1;i<=n;i++)
 77     {
 78         scanf("%s",tmp);
 79         D[i]=tmp;leng[i]=D[i].length()-1;
 80     }
 81     for(int i=1;i<=n;i++)insert(1,i,0);
 82 //    fprintf(stderr,"tot%d\n",tot);
 83     root[0]=++stot;
 84     dfs(1);
 85 //    fprintf(stderr,"stot%d\n",stot);
 86     scanf("%d",&m);
 87     for(int i=1;i<=m;i++)
 88     {
 89         scanf("%s%s",s1,s2);
 90         l1=strlen(s1);l2=strlen(s2);l1--;l2--;
 91         for(int i=0;i<=l1;i++)
 92         s1[i]=char((int(s1[i]-'a')+ans)%26+(int)'a');
 93         for(int i=0;i<=l2;i++)
 94         s2[i]=char((int(s2[i]-'a')+ans)%26+(int)'a');
 95         x=match(1);
 96         ans=match(root[Eu[x]+size[x]-1],root[Eu[x]-1]);
 97         printf("%d\n",ans);
 98     }
 99     return 0;
100 }

 

推荐阅读