@poorpool
2017-11-07 10:57
字数 1834
阅读 933
%%%zrt
水题。
求最长不降子序列,个数>=n-1即可。
或者降则删数。
30分:枚举x。
60分:中国剩余定理。
M = a1a2a3a4
x = M/a1*ni(M/a1, a1)*b1+...
(求逆元法:exgcd)
100:exgcd两两合并
x+a1k1=b1
x+k2a2=b2
a1k1-a2k2=b1-b2
exgcd(a1,-a2,k1,k2)
发现回文串可二分。即:中心扩散。
本质不同的回文串个数一共O(n)个。
求了个哈希。
就是一个字符串到整数的映射。
快速比较两个字符串是否相等。
hash相等很有可能相等。
hash不等必定不等。
常用rk-hash。
把字符串看做一个base进制数,对素数取模。
hash[i]=(hash[i-1]*base+s[i])%p
hash[i]:1~i的hash值。
base取31,131,13131之类都可以。
注意a映射到1而非0。
p要是素数(最好long long),像什么1e18+9,23333333333333333(16个3)
unsigned long long自然溢出可看做对取模,但会被特殊构造卡掉。
不放心可以多找几个素数同时算。
123456求345
先求12345
再求12000
欲求s[l~r]的hash
先hash[r]
再hash[l-1]*
123 456 -> 123456
123000+456
abcde
abcef
->
abc
1表示hash相同,0表示hash不同,则对于长度相同的串,必有
1111...10...0000
二分即可。
单模式串匹配算法。
自己百度。
abcbaabcba
求以每个字符为中心能扩展多远
1131111311
暴力:
for(int i=1; i<=l; i++){
r[i] = 1;
while(s[i-r[i]]==s[i+r[i]])
r[i]++;
}
优化
int mx=max(i+r[i]-1)
int id//mx取到最大值时的i
//i走了一点...
//example:aabacabac
when i>id i<mx
//对称过去
i <--value--- id-(i-id)
//r[i]表示以i为中心能扩展的距离
///////////////code/////////////
for(int i=1; i<=l; i++){
r[i] = min(r[id-(i-id)], mx-i);
//因为r[id-(i-id)]可能向左扩展出了id管辖的范围,范围外不受id管辖
while(s[i-r[i]]==s[i+r[i]])
r[i]++;
if(i+r[i]-1>mx){
mx = i+r[i]-1;
id=i;
}
}
欲求a串每个后缀跟b串的lcp。
先求b串每个后缀和自己的lcp。
暴力
for(int i=1; i<=n; i++){
p[i] = 0;
while(b[i+p[i]]==b[p[i]+1])
p[i]++;
}
//等号两边 前一个为后缀,后一个为前缀
优化
for(int i=1; i<=n; i++){
p[i] = min(mx-i,p[i-id]);
while(b[i+p[i]]==b[p[i]+1])
p[i]++;
if(i+p[i]>mx){
id = i;
mx = i+p[i];
}
}
每个节点代表一个字符串
int trie[100005][26];
int tot;
//root=0
void instert(char * s){
int p0;
for(int i=0;s[i];i++){
if(trie[p][s[i]-'a'])
id=trie[p][s[i]-'a'];
else
id=trie[p][s[i]-'a']=++tot;
}
flag[p]++;
}
trie树dfs序为这些串的字典序
lcp=lca深度
trie图
trie树上不存在的孩子用它fail节点的孩子补出来
fail节点的概念与kmp的next类似
可用一次bfs来求
若trie[i][x]存在,则fail[trie[i][x]]=trie[fail[i]][x]
否则trie[i][x]