「BZOJ3483 / 4212」SGU505 Prefixes and suffixes(询问在线版)
Description
GAL发现了N个特殊的字母序列，由小写字母组成。小L认为，对于两个字符串s1,s2，若s1是某个特殊序列的前缀，s2是该特殊序列的后缀，则称s1,s2被这个序列拥有。
现在小L给出M对s1,s2，对于每对字符串，问它们被几个特殊序列拥有。
Input
第1行一个整数N。
接下来N行，每行一个字符串，代表N个特殊序列。
第N+2行一个整数M。
接下来M行每行一对s1,s2用空格隔开。S1,s2是经过加密的。
设上一问的答案为lastans。解密方法是将s1,s2所有字母向后移动lastans个单位，这时你要把小写字母表当作一个环，比如z的下一个字母是a。
Output
对于每次询问操作，输出一个非负整数表示答案。
Sample Input
3
aaaaa
abacabaa
avtobus
6
a a
y yy
yy y
zzzzz zzzz
zazb bzaz
abac a
Sample Output
2
2
1
1
0
1
HINT
设N个特殊序列总长为L1，所有M组询问总长为L2。L1，L2<=2000000.N<=2000,M<=100000
题解
「FJ2015集训」神牛养成计划
听说不怎么卡暴力，就交了个自然溢出，结果一看，别人哈希都是70分
我40分，代码太丑自带常数大
正解出题人给出的是可持久化trie
卓神现场用神做法ac：对于询问俩串长都小于20的，可知这种类型有解的情况只有2000*20*20种，把这些情况预处理答案用map存一下，然后直接查表
其余的暴力
100分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<map> #include<set> #include<cstdio> #include<cstring> #include<vector> #include<cstdlib> #include<iostream> #include<algorithm> #define ll long long using namespace std; int n,m; string a[2005]; vector<unsigned ll>L[2005],R[2005]; int l[2005]; char ch[2000005]; void pre() { unsigned ll last; for(int i=1;i<=n;i++) { last=17; for(int j=0;j<l[i];j++) { last=last*1000000007+a[i][j]; L[i].push_back(last); } } for(int i=1;i<=n;i++) { last=17; for(int j=0;j<l[i];j++) { last=last*1000000007+a[i][l[i]-j-1]; R[i].push_back(last); } } } int main() { // freopen("godcow.in","r",stdin); // freopen("godcow.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%s",ch); l[i]=strlen(ch); for(int j=0;j<l[i];j++)a[i]+=ch[j]; } pre(); scanf("%d",&m); int ans=0; for(int i=1;i<=m;i++) { unsigned ll x=17,y=17; scanf("%s",ch); int l1=strlen(ch); for(int j=0;j<l1;j++)ch[j]=(ch[j]-'a'+ans)%26+'a'; for(int j=0;j<l1;j++)x=x*1000000007+ch[j]; scanf("%s",ch); int l2=strlen(ch); for(int j=0;j<l2;j++)ch[j]=(ch[j]-'a'+ans)%26+'a'; for(int j=0;j<l2;j++)y=y*1000000007+ch[l2-j-1]; ans=0; for(int j=1;j<=n;j++) if(L[j][l1-1]==x) if(R[j][l2-1]==y) ans++; printf("%d\n",ans); } return 0; } |
计数器 9854494
OI 课件=>
OI 课件=>
呀啦呀啦，贴了两份没区别的代码呢。。
两份代码真的有区别么
请问Ag±60中的Ag是什么意思呢？