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. 主席树
具体可参考模板(可持久化线段树):https://ji-suan-ke.blog.luogu.org/post-mu-ban-ke-chi-jiu-hua-xian-duan-shu
具体可参考模板(可持久化数组):https://ji-suan-ke.blog.luogu.org/post-mu-ban-ke-chi-jiu-hua-shuo-zu
2. AC自动机
具体可参考模板:https://ji-suan-ke.blog.luogu.org/post-mu-ban-ac-zi-dong-ji
3. 二维凸包
具体可参考模板:https://ji-suan-ke.blog.luogu.org/post-mu-ban-er-wei-tu-bao
4. FFT快速傅里叶变换
具体可参考模板:https://ji-suan-ke.blog.luogu.org/post-mu-ban-fft
未掌握算法
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 出好成绩。
0 条评论