2019.3 长郡省选集训算法总结

所有涉及算法

1. 树链剖分求LCA(之前已经掌握)

2. 主席树(可持久化线段树)

3. 点分治

4. 网络流相关(费用流，最大流，最小割，最值闭合子图等)

5. 几何相关(二维凸包等)

6. 多项式乘法快速傅里叶变换(FFT)及分治FFT

7. 后缀数组

8. 莫比乌斯反演

9. 平衡树(Treap,Splay等)

10. AC自动机

11. 容斥原理

12. 线性基(关于多数异或操作的数据结构)

已掌握并运用的算法

1. 树链剖分求LCA

具体可参考模板：https://ji-suan-ke.blog.luogu.org/post-mu-ban-zhang-lian-pou-fen-xing-shi-lca

2. 网络流相关的算法

这些算法关键在于怎么建图，算法本身可以参考计蒜客的课程

3. 线性基

具体可参考模板：https://ji-suan-ke.blog.luogu.org/post-mu-ban-xian-xing-ji

已掌握但不知道怎么运用的算法

未掌握算法

1. 后缀数组

2. 莫比乌斯反演

3. 点分治

4. 平衡树

5. 容斥原理

算法模板及典型例题

1. 树链剖分求LCA

这个方法可以比倍增求LCA常数更优，并且省去了求倍增数组的麻烦之处。方法也很清楚明了，重点是要搞清楚以下数组的定义和用处：

$hson[maxn]$ 表示一个节点的重儿子，若所有儿子的重量相同，可认为 $hson[]$ 为其中任意一个

$top[maxn]$ 表示一个节点所处的链的顶端，在求LCA时每次都是链顶深的一个点往上跳

其他的像是 $fa[maxn],sz[maxn]$ 含义很清楚，这里不做赘述

例题有：洛谷P3379 之前用倍增过的试着用树剖写一遍

优秀的题解有：https://www.luogu.org/problemnew/solution/P3384

模板在这里（只写了LCA没有写线段树）：

#include <bits/stdc++.h>
using namespace std;
int n,m,s;
const int maxn = 500010;
struct edge{
    int v,nxt;
}E[maxn*2];
int p[maxn],eid;
void init(){
    memset(p,-1,sizeof p);
    eid = 0;
}
void insert(int u,int v){
    E[eid].v = v;
    E[eid].nxt = p[u];
    p[u] = eid++;
}
void insert2(int u,int v){
    insert(u,v);
    insert(v,u);
}
int fa[maxn],dep[maxn],sz[maxn],hson[maxn];
void dfs1(int u){
    sz[u] = 1;
    dep[u] = dep[fa[u]] + 1;
    for(int i=p[u];~i;i=E[i].nxt){
        int v = E[i].v;
        if(v != fa[u]){
            fa[v] = u;
            dfs1(v);
            sz[u] += sz[v];
            if(sz[v] > sz[hson[u]]){
                hson[u] = v;
            }
        }
    }
}
int top[maxn];
void dfs2(int u,int tp){
    top[u] = tp;
    if(hson[u]){
        //有重儿子就走重儿子
        dfs2(hson[u],tp); 
    }
    for(int i=p[u];~i;i=E[i].nxt){
        int v = E[i].v;
        if(v != fa[u] && v != hson[u]){
            dfs2(v,v);
        }
    }
}
int lca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] > dep[top[y]]) swap(x,y);
        y = fa[top[y]];
    }
    return dep[x] < dep[y] ? x : y;
}
int main(){
    init();
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n-1;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        insert2(u,v);
    }
    dfs1(s);
    dfs2(s,s);
    for(int i=1;i<=m;i++){
        int xx,yy;
        scanf("%d%d",&xx,&yy);
        printf("%d\n",lca(xx,yy));
    }
    return 0;
}

2. 线性基

线性基是一种数据结构，它用于解决类似 求一堆数异或起来最大值可能为多少 的问题。

它维护了一个数组 $p[maxbit]$ 其中 $maxbit$ 为这一堆数中最大数的二进制位数。它有一个重要的性质，就是你把 $p[]$ 里面的数随意组合异或，得到的值域与原来那一堆数随便组合异或的值域相同。

因此可以贪心的用 $p[]$ 来计算原来那一堆数异或起来的最大值。从高到低取 $p[]$ 数组的每一个元素，如果异或上当前这个数能使答案更大就异或上这个数。

至于构造计算 $p[]$ 的过程，过于玄学，不想去研究，直接背模板吧，挺简单的。

模板在这里：

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 50;
const int maxbit = 64;
int n;
ll a[maxn],p[maxbit];
int main(){
    scanf("%d",&n);
    memset(a,0,sizeof a);
    memset(p,0,sizeof p);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
        //构造线性鸡
        for(int j=62;j>=0;j--){
            if(!(a[i]>>j)) continue;
            if(!p[j]){
                p[j] = a[i];
                break;
            }
            a[i] ^= p[j];
        } 
    }
    ll ans = 0;
    for(int i=62;i>=0;i--){
        ans = max(ans,ans^p[i]);
    }
    printf("%lld",ans);
    return 0;
}

还有个问题，就是说判断当前线性基中的所有数随意组合，能否异或组成某个数，该如何判断。这个问题也不难，就假装再把要判断的数插入线性基，如果能插入表示不能构造出，不能插入表示能构造出。具体见线性基题解：https://www.luogu.org/problemnew/solution/P3812

3. AC自动机

这个我觉得用到的地方不是很多，也可能我没做过太多关于这个算法的题，所以我就只简单介绍一下这个算法是用来干嘛的，然后给出模板。

具体为什么这么做以后可以深入探讨，这里不做讲述。

AC自动机用于解决一类 多模式串字符串匹配问题 ，你可以把它看成是KMP算法的升级版。KMP是在一个文本串中寻找 一个模式串 出现位置，而AC自动机可以解决在一个文本串中寻找 多个模式串 的出现位置，比如下列问题:

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
$∑length(模式串)<=10^6$
$∑length(文本串)<=10^6$

AC自动机本质是在Trie树上跑KMP，它将多个模式串放在一棵Trie树上，在匹配的时候就可以兼顾到多个模式串，达到提升效率的效果，至于Fail数组如何处理等等可参考这篇题解：http://www.cnblogs.com/cjyyb/p/7196308.html

我写的模板：

#include <bits/stdc++.h>
using namespace std;
const int maxlen = 1000010;
namespace Trie{
    struct node{
        int fail,cnt,nxt['z'-'a'+2];
        node(){memset(nxt,0,sizeof nxt);}
    }trie[maxlen];
    int tid = 0;
    void insert(int id,char *str){
        int len = strlen(str);
        for(int i=0;i<len;i++){
            int now = str[i] - 'a';
            if(trie[id].nxt[now] == 0){
                //new node
                trie[id].nxt[now] = ++tid;
            }
            id = trie[id].nxt[now];
        }
        trie[id].cnt++;
    }
}
namespace ACAuto{
    void getFail(int id){
        queue<int> q;
        for(char c='a';c<='z';c++){
            int now = Trie::trie[id].nxt[c-'a'];
            if(now){
                q.push(now);
                Trie::trie[id].fail = id;
            }
        }
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(char c='a';c<='z';c++){
                int v = Trie::trie[u].nxt[c-'a'];
                if(!v) {
                    Trie::trie[u].nxt[c-'a'] = Trie::trie[Trie::trie[u].fail].nxt[c-'a'];
                    continue;
                }
                Trie::trie[v].fail = Trie::trie[Trie::trie[u].fail].nxt[c-'a'];
                q.push(v);
            }
        }
    }
    
    long long query(int id,char *str){
        long long ans = 0;
        int len = strlen(str);
        for(int i=0;i<len;i++){
            int now = Trie::trie[id].nxt[str[i]-'a'];
            while(now && Trie::trie[now].cnt != -1){
                ans += Trie::trie[now].cnt;
                Trie::trie[now].cnt = -1;
                now = Trie::trie[now].fail;
            }
            id = Trie::trie[id].nxt[str[i]-'a'];
        }
        return ans;
    }
}
int n;
char tmp[maxlen];
int main(){
    //freopen("testdata.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",tmp);
        Trie::insert(0,tmp);
    }
    ACAuto::getFail(0);
    scanf("%s",tmp);
    printf("%lld\n",ACAuto::query(0,tmp));
    return 0;
}

最后

有一些算法我自己都还弄得不是很明白，所以没有在后面放出来，如果大家想学可以在洛谷上搜模板题来做，欢迎探讨。

祝大家在NOI(Piao)2019 Piao 出好成绩。

手机上阅读

最后一次更新于2020-03-16

BobH's Blog

A new blog