清北学堂金秋营 day6

%%%zrt

题解

T1

水题。

求最长不降子序列，个数>=n-1即可。

或者降则删数。

T2

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)

T3

发现回文串可二分。即：中心扩散。
本质不同的回文串个数一共O(n)个。
求了个哈希。

字符串

常用

• hash
• kmp
• manacher

字符串hash

就是一个字符串到整数的映射。
快速比较两个字符串是否相等。

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自然溢出可看做对$\ 2^{64}$取模，但会被特殊构造卡掉。

不放心可以多找几个素数同时算。

求任意一段的hash?

123456求345
先求12345
再求12000
欲求s[l~r]的hash
先hash[r]
再hash[l-1]*$\ base^{r-l+1}$

求连接起来的hash？

123 456 -> 123456
123000+456

求最长公共前缀（lcp）？

abcde
abcef
->
abc

1表示hash相同，0表示hash不同，则对于长度相同的串，必有
1111...10...0000
二分即可。

KMP

单模式串匹配算法。

自己百度。

manacher

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;
    }
}

exKMP

欲求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];
    }
}

字典树（trie树）

每个节点代表一个字符串

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深度

AC自动机

trie图

trie树上不存在的孩子用它fail节点的孩子补出来

fail节点的概念与kmp的next类似
可用一次bfs来求

若trie[i][x]存在，则fail[trie[i][x]]=trie[fail[i]][x]
否则trie[i][x]