Chlience

【算法】NOIP前的一些板子
数据结构ST表将原区间变成两段拼起来,这两段可以重叠int prepare() { for(int i =...
扫描右侧二维码阅读全文
25
2018/10

【算法】NOIP前的一些板子

数据结构

ST表


将原区间变成两段拼起来,这两段可以重叠

int prepare() {
    for(int i = 1 ; i <= log2(n) + 1 ; i ++)
        for(int j = 1 ; j + (1 << i) - 1 <= n ; ++ j)
            a[j][i] = max(a[j][i - 1] , a[j + (1 << (i - 1))][i - 1]);
}
int query(int l , int r) {
    int k = log2(r - l + 1);
    return max(a[l][k] , a[r - (1 << k) + 1][k]);
}

树状数组


掌握好 lowbit ,熟练使用各种变形
核心思想:差分
修改单点,查询前缀和

int lowbit(int x) {return x & (-x);}
void add(int pos , int x) {for(; pos <= n ; pos += lowbit(pos)) a[x] += pos;}
int query(int pos) {int ans = 0; for(; pos ; pos -= lowbit(pos)) ans += a[x]; return ans;}

线段树


将区间二分构建

void build(int x , int l , int r) {
    if(l == r) {a[x] = l;}
    else {
        build(L , l , mid);
        build(R , mid + 1 , r);
    }
}

哈希表


将大区间映射到小区间,MAP更为常用
建议使用双哈希

int find(x) {
    int now = x % mod;
    while(num[now] != x && vis[now]) now = (now + 17) % mod;
    return now;
}


比较难打,但是一般还是手写为主

void push(int x) {
    heap[++ cnt] = x;
    int temp = cnt;
    while(temp / 2) {
        if(heap[temp] < heap[temp / 2]) {
            swap(heap[temp] , heap[temp/2]);
            temp /= 2;
        }
        else break;
    }
}
void pop() {
    heap[1] = 0;
    heap[1] = heap[cnt];
    heap[cnt -- ] = 0;
    int temp = 1 , son = 2 ;
    while(son <= cnt) {
        if(son + 1 <= cnt && heap[son + 1] < heap[son]) ++ son;
        if(heap[temp] > heap[son]) {
            swap(heap[temp],heap[son]);
            temp = son;
        }
        else break;
    }
}

单源最短路


一般使用 Dijkstra ,当然是要套线段树的

void dijistra() {
    for(int i = 1 ; i < n ; ++ i) {
        int now = t.pos[1];
        for(int j = head[now] ; j ; j = e[j].n) {
            if(dis[e[j].t] > dis[now] + e[j].w) {
                dis[e[j].t] = dis[now] + e[j].w;
                t.change(1 , 1 , n , e[j].t , dis[e[j].t]);
            }
        }
        t.change(1 , 1 , n , now , INT_MAX);
    }
}

并查集


用一个点来表示一个集合,一般用于维护连通性问题

int find(int x) {return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);} //路径压缩
int find(int x) {while(x != fa[x]) x = fa[x]; return x;} //非路径压缩非递归

强连通分量


互相可达的点叫做强连通分量

void dfs(int x){
    low[x] = dfn[x] = ++ p; vis[x] = 1;
    sta[++ top] = x;
    for(int i = head[x] ; i ; i = e[i].n){
        int to = e[i].t;
        if(!dfn[to]) {
            dfs(to);
            low[x] = min(low[x] , low[to]);//调整最高点位置
        }
        else if(vis[to])
            low[x] = min(low[x] , dfn[to]);//出现过就从上面更新下
    }
    if(dfn[x] == low[x]){
        hash[x] = ++ tot;
        vis[x] = 0;
        for(; sta[top] != x ; -- top){
            hash[sta[top]] = tot;
            vis[sta[top]] = 0; 
        }
        -- top;
    }
    return ;
}

拓扑排序


按照从外到内、先子后父的关系排序,方便处理,常用于DP

while(!q.empty()) {
    int now = q.front(); q.pop();
    for(int i = head[x] ; i ; i = e[i].n)
        if(-- in[e[i].t] == 0)
            q.push(e[i].t)
}

LCA


一般直接套用倍增算法

int lca(int x,int y) {
    if(deep[x] < deep[y]) swap(x , y);
    for(int i = top ; i >= 0 ; -- i)
        if(deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
    if(x == y) return x;
    for(int i = top ; i >= 0 ; -- i)
        if(fa[x][i] != fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    return fa[x][0];
}

DFS序


子树中的节点 dfs 序在祖先节点区间内

void dfs(int x) {
    l[x] = ++ cnt;
    for(int i = head[x] ; i ; i = e[i].n)
        dfs(e[i].t)
    r[x] = cnt;
}

字符串

KMP


字符串匹配算法,方便的匹配一个串是否在另一个串中出现过

while(r < lenths) {
    if(l == -1 || s[l] = s[r]) nxt[++ r] = ++ l;
    else l = nxt[r];
}
while(r < lentht) {
    if(l == -1 || s[l] == t[l]) {++ l; ++ r;}
    else l = nxt[l];
    if(l == lenths) {}
}

manacher


高效算出回文串的方法,一般要插入特殊字符

for(int i = 0 ; i < n ; ++ i) {
    str[++ top] = s[i];
    str[++ top] = '#';
}
for(int i = 1 ; i <= top ; ++ i) {
    if(i < r) p[i] = min(p[pos * 2 - i] , r - i);
    else p[i] = 1;
    while(str[i + p[i]] == str[i - p[i]]) ++ p[i];
    if(i + p[i] > r) {r = i + p[i]; pos = i;}
    ans = max(ans , p[i] - 1);
}

数学

gcd


最大公因数

int gcd(int a , int b) {return b ? gcd(b , a % b) : a;}

lcm


最小公倍数

int lcm(int a , int b) {return a * b / gcd(a , b);}

快速幂


int qpow(int a , int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return ans;
}

矩阵


一定要记得 左乘 左乘 左乘!

for(int i = 0 ; i < n ; ++ i)
    for(int j = 0 ; j < n ; ++ j)
        for(int k = 0 ; k < n ; ++ k)
            ans[i][j] += a[i][k] * b[k][j];

逆元


线性 or 单个

void getinv(int n) {
    inv[1] = 1;
    for(int i = 2 ; i <= n ; ++ i)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
}
int getinv(int x) {return qpow(x , mod - 2);}

组合数


组合数一般直接杨辉三角或者线性搞

void prepare(int x) {
    inv[1] = proinv[1] = pro[1] = 1;
    for(int i = 2 ; i <= n ; ++ i) {
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        proinv[i] = 1ll * proinv[i - 1] * inv[i] % mod;
        pro[i] = 1ll * pro[i - 1] * i % mod;
    }
}
int C(int n , int m) {return 1ll * pro[n] * proinv[m] % mod * priinv[n - m] % mod;}
Last modification:October 31st, 2018 at 03:40 pm

Leave a Comment