相信大家初步了解了倍增之后,想要实践一下。这里选取了牛客的例题来讲解。来个👍 呗,

  • 入门知识传送门
  • 一些简单规定
    • 指图上的最短路,在树上为 的简单路径。
    • 指有根树上的深度。

[AHOI2008]MEET 紧急集合

题意

给出三个点 ,找到一个节点 使 最小。

分析

我们考虑两个节点,那么比较简单,只要不走回头路就是最短的,换而言之就是 上的任意一个节点就可以。那么两个节点可以这样做,三个节点呢?我们可以类比,只要 这三条路径没有重叠,那么这样的 点就是合法的。那么现在如何找这个 点,对于 中任意两个点来说,只要 在简单路径上就可以了。那么我们可以分类讨论。

  • 如果 ,那么由于 上,则 必然是 的祖先,或者子树。那么等同于 ,或者

  • 那么容易得到 两两求出 那么必然存在两个 是相同的,那么另一个 就是最优答案,那么剩下的就是树上距离公式了 。考虑倍增求 ,那么总的复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 5e5 + 100;
struct Edge {int to,nxt;}e[N << 1];
int Log[N],fa[N][21],dep[N],head[N],n,m,ecnt;
void add(int x,int y) {e[++ecnt] = (Edge){y,head[x]};head[x] = ecnt;}
int lca(int a,int b) {
    if(dep[a] < dep[b]) swap(a,b);int k = dep[a] - dep[b];
    for(int i = Log[k];~i;i--) if((k >> i) & 1) a = fa[a][i];
    if(a == b) return a;
    for(int i = Log[dep[a]];~i;i--) if(fa[a][i] ^ fa[b][i]) a = fa[a][i],b = fa[b][i];
    return fa[a][0];
}
void dfs(int x,int F,int D) {
    fa[x][0] = F;dep[x] = D;
    for(int i = 1;i <= Log[dep[x]];i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(int i = head[x];i;i = e[i].nxt) {int y = e[i].to;if(y == F) continue;dfs(y,x,D + 1);}
}
int tdis(int a,int b) {return dep[a] + dep[b] - 2 * dep[lca(a,b)];}
int solve(int x,int a,int b,int c) {
    return tdis(x,a) + tdis(x,b) + tdis(x,c);
}
int main() {
    n = read();m = read();
    for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
    for(int i = 1,a,b;i < n;i++) {
        a = read();b = read();
        add(a,b);add(b,a);
    }
    dfs(1,0,1);
    while(m--) {
        int a = read(),b = read(),c = read(),ans = 0,dis = 0;
        int t1 = lca(a,b),t2 = lca(b,c),t3 = lca(a,c);
        if(t1 == t2) ans = t3,dis = solve(t3,a,b,c);
        if(t1 == t3) ans = t2,dis = solve(t2,a,b,c);
        if(t2 == t3) ans = t1,dis = solve(t1,a,b,c);
        printf("%d %d\n",ans,dis);
    }
}

疫情控制

题意

给你一个有根树,根节点为 ,要求同时调动多支军队,使军队出现任意叶子节点到 的路径上( 号节点不能出现军队)。求时间的最小值。

分析

由于你可以同时调动,那么其实就使求最大调度时间最小,那么这个可以考虑二分答案,将问题转化为判断问题。那么现在就是考虑在 的情况下是否可以使军队出现在任意叶子节点到 的路径上。

  • 贪心,我们可以容易想到,由于可以同时调动,那么对于任意一支军队,都要使他尽量的往上,因为这样不会使答案更劣,但是这里我们并不能慢慢跳父亲,而且考虑倍增,考虑的方式可以类比倍增求 的过程,而且同时保存 的答案。

  • 我们做完上一步,现在发现,军队被划分成两种。

    • 可以到达 号节点。
    • 不可以到达 号节点。
  • 那么我们先对所有子树遍历,考虑这个子树是否可以不需要军队了。那么最后我们剩下的就是,一些还需要军队来出现的子树和一些搁置在 号节点的军队。对于每个子树我们记录它的根节点到 的距离为 ,和每一支可以到达 号节点还剩余的时间 。那么现在问题转化为。是否可以在 序列中选取 个元素,使 满足 。这个可以考虑贪心,将 都从小到大排序,维护两个指针

    • 如果 的子树需要一个军队,那么我们可以考虑不让 跳到 号节点,直接使 的子树变为已覆盖,因为每一个没有被覆盖的子树至少需要一个军队到覆盖,那么在 还没有被访问时覆盖,这样一定可以使答案不更劣。
    • 如果 直接覆盖,考虑下一个
    • 如果 ,考虑下一个

最后判断所有子树都被覆盖就可以了,这样总的复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 51010,inf = 0x3f3f3f3f;
struct Edge {int to,nxt,w;}e[N << 1];
int Log[N],head[N],f[N][21],g[N][21],dep[N],m,n,ecnt;
void add(int x,int y,int w) {e[++ecnt] = (Edge){y,head[x],w};head[x] = ecnt;}
void Init(int x,int fa,int de,int dis) {
    dep[x] = de;f[x][0] = fa;g[x][0] = dis;
    for(int i = 1;i <= Log[de];i++) f[x][i] = f[f[x][i - 1]][i - 1],g[x][i] = g[f[x][i - 1]][i - 1] + g[x][i - 1];
    for(int i = head[x];i;i = e[i].nxt) {int y = e[i].to;if(y ^ fa) Init(y,x,de + 1,e[i].w);}
}
int Id[N],sub[N],top,Top;
bool vis[N];
pii st[N],St[N];
void init(int x,int fa,int Sub) {sub[x] = Sub;for(int i = head[x];i;i = e[i].nxt) if(e[i].to ^ fa) init(e[i].to,x,Sub);}
void solve(int x) {
    bool P = 1;if(vis[x]) return;
    for(int i = head[x];i;i = e[i].nxt) {
        int y = e[i].to;if(y == f[x][0]) continue;
        P = 0;solve(y);if(x != 1 && vis[y] == 0) return;
    } if(x != 1 && P == 0) vis[x] = 1;
}
int getk(int x,int tot,int &z) {
    z = 0;for(int i = Log[dep[x]];~i;i--) {
        if(f[x][i] && g[x][i] <= tot) tot -= g[x][i],z += g[x][i],x = f[x][i];
    }return x;
}
bool check(int mid) {
    memset(vis,0,sizeof(vis));top = 0;Top = 0;
    for(int i = 1;i <= m;i++) {
        int x = Id[i],t;
        x = getk(x,mid,t);
        if(x != 1) vis[x] = 1;
        else st[++top] = pii(mid - t,sub[Id[i]]);
    }solve(1);
    for(int i = head[1];i;i = e[i].nxt) {
        int y = e[i].to;if(vis[y]) continue;
        St[++Top] = pii(e[i].w,e[i].to);
    }
    sort(st + 1,st + 1 + top);sort(St + 1,St + 1 + Top);
    int id = 1;
    for(int i = 1;i <= top;i++) {
        if(!vis[st[i].second]) vis[st[i].second] = 1;
        else if(st[i].first >= St[id].first) vis[St[id].second] = 1;
        while(vis[St[id].second] && id <= Top) ++id;
    }
    return id > Top;
}
int main() {
    n = read();
    for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
    for(int i = 1;i < n;i++) {
        int a = read(),b = read(),c = read();
        add(a,b,c);add(b,a,c);
    }
    Init(1,0,1,0);
    for(int i = head[1];i;i = e[i].nxt) init(e[i].to,1,e[i].to);
    m = read();int res = m;
    for(int i = 1;i <= m;i++) Id[i] = read();
    for(int i = 1;i <= n;i++) res -= (dep[i] == 2);
    if(res < 0) {printf("-1\n");return 0;}
    else {
        int l = 0,r = inf,ans = 0;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(check(mid)) ans = mid,r = mid - 1;
            else l = mid + 1;
        }printf("%d\n",ans);return 0;
    }
}

A and B and Lecture Rooms

题意

给你俩个节点 和一棵无根树,找出树上满足 的节点个数。

分析

我们比较好思考的就是 至多只有一个合法点,而且这个合法点一定是满足 的,所以当 时是一定无解的。那么我们现在考虑 的节点位置,比较好分析的是 只会在 处发生一次转折,所以 中深度较深的祖先,具体来讲是它的 级祖先 。现在只需要讨论 的关系就好了。

  • 那么要使 ,那么可以选择的节点就是,所有的节点除去以 为根的, 所在的两个子树的所有节点。
  • 那么要使 ,那么可以选择的节点就是,以祖先 为根的子树中,除去深度较深的 所处的子树节点。

那么总的复杂度为 ,因为我们需要查找 级祖先和查找

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 1e5 + 100;
struct Edge {int to,nxt;}e[N << 1];
int fa[N][21],siz[N],dep[N],Log[N],n,head[N],ecnt;
void add(int x,int y) {e[++ecnt]=(Edge){y,head[x]};head[x]=ecnt;}
int get(int x,int k) {
    for(int i = Log[k];~i;i--) if((k >> i) & 1) x = fa[x][i];
    return x;
}
int lca(int x,int y) {
    if(dep[x] < dep[y]) swap(x,y);int k = dep[x] - dep[y];
    x = get(x,k);if(x == y) return x;for(int i = Log[dep[x]];~i;i--) {
        if(fa[x][i] ^ fa[y][i]) x = fa[x][i],y = fa[y][i];
    }return fa[x][0];
}
void dfs(int x,int F,int D) {
    siz[x] = 1;fa[x][0] = F;dep[x] = D;
    for(int i = 1;i <= Log[dep[x]];i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(int i = head[x];i;i = e[i].nxt) 
    {int y = e[i].to;if(y == F) continue;dfs(y,x,D + 1);siz[x] += siz[y];}
}
int main() {
    n = read();
    for(int i = 2;i <= n;i++) Log[i] = Log[i >> 1] + 1;
    for(int i = 1;i < n;i++) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }
    dfs(1,0,1);int Q = read();
    while(Q--) {
        int x = read(),y = read(),z = lca(x,y);
        if(x == y) printf("%d\n",n);
        else if(dep[x] == dep[y]) {
            int k = dep[x] - dep[z] - 1;
            x = get(x,k);y = get(y,k);
            printf("%d\n",n - siz[x] - siz[y]);
        }
        else {
            int len = dep[x] + dep[y] - dep[z] * 2;
            if(len % 2) printf("0\n");
            else {
                if(dep[x] < dep[y]) swap(x,y);
                z = get(x,len / 2);x = get(x,len / 2 - 1);
                printf("%d\n",siz[z] - siz[x]);
            }
        }
    }
}

[SCOI2015]国旗计划

题意

给出 条线段,要求覆盖完整个环。求出某一条必选之后,至少需要的线段数量,线段无包含关系。

分析

常见的破环成链,那么我们把链倍长一次,现在就是要覆盖长度为 的序列就可以了。那么由于线段没有包含关系,那么线段相离或者有交集。那么我们按左端点排序,得到的区间右端点应该是递增的。这样我们就可以贪心,显然,如果我们要从一个区间转移到另一个区间,那么另一个区间的右端点一定是,所有左端点小于当前右端点的所有区间中的最大值。那么我们的每一次跳跃是固定的,这里我们就可以考虑用倍增来维护,这样单次询问的时间复杂度为 加上离散化的复杂度,总的复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 8e5 + 1000;
struct Node {int l,r;}q[N],rq[N];
int B[N],nxt[N][21],n,m,tot,top;
bool cmp(Node a,Node b) {return a.l < b.l;}
int main() {
    n = read();m = read();
    for(int i = 1;i <= n;i++) {
        int l = read(),r = read();
        q[i] = (Node){l,r};
        if(r < l) rq[++tot] = (Node) {l,r + m}, rq[++tot] = (Node) {l + m,m * 2};
        else rq[++tot] = (Node) {l,r}, rq[++tot] = (Node) {l + m,r + m};
    }
    for(int i = 1;i <= tot;i++) B[++top] = rq[i].l , B[++top] = rq[i].r;
    sort(B + 1,B + 1 + top);top = unique(B + 1,B + 1 + top) - B - 1;
    sort(rq + 1,rq + 1 + tot,cmp); 
    for(int i = 1,r = 0,l = 1;i <= top;i++) {
        while(l <= tot && rq[l].l <= B[i]) r = max(rq[l].r,r),l++;
        nxt[i][0] = lower_bound(B + 1,B + 1 + top,r) - B;
//        cout << nxt[i][0] << " " << top << endl;
    }
    for(int i = 1;i <= 20;i++) {
        for(int j = 1;j <= top;j++) nxt[j][i] = nxt[nxt[j][i - 1]][i - 1];
    }
    for(int i = 1;i <= n;i++) {
        if(q[i].l > q[i].r) q[i].r += m;int ans = 1;
        int pos = lower_bound(B + 1,B + 1 + top,q[i].r) - B;
        for(int j = 20;~j;j--) {
            if(B[nxt[pos][j]] < q[i].l + m) {
                ans += (1 << j);pos = nxt[pos][j];
            }
        }
        ans++;printf("%d ",ans);
    }printf("\n");
    return 0;
} 

Smile House

题意

给你一张有向图,求出最小节点个数的正环。

分析

由于我不喜欢正环,代码中把每条边的权值取反,求的是负环,分析也采用负环分析。我们考虑直接枚举点数来转移,定义 表示,考虑 个点,从 的最短路,那么如果出现负环 。但是这样复杂度为 的,考虑弗洛伊德最短路,弗洛伊德的转移矩阵,每次是相同的,那么我们可以考虑把 的转移矩阵存下来,那么再二分一个答案,这样复杂度就是 了,其实任意可以从单调性分析,我们从大到小枚举 中的 ,这样复杂度就可以减低到 了,分析可以类比 的分析(见入门知识)。

代码

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 310;
int f[12][N][N],last[N][N],now[N][N],n,m;
int main() {
    n = read();m = read();
    memset(f,0x3f,sizeof(f));
    for(int i = 1;i <= n;i++) f[0][i][i] = 0;
    for(int i = 1;i <= m;i++) {
        int a = read(),b = read(),c = -read(),d = -read();
        f[0][a][b] = c;f[0][b][a] = d;
    }
    for(int l = 1;l <= 10;l++) {
        for(int k = 1;k <= n;k++) {
            for(int i = 1;i <= n;i++) {
                for(int j = 1;j <= n;j++) {
                    f[l][i][j] = min(f[l][i][j],f[l - 1][i][k] + f[l - 1][k][j]);
                }
            }
        }
    }
    memset(last,0x3f,sizeof(last));
    for(int i = 1;i <= n;i++) last[i][i] = 0;
    int ans = 0,ss = 0;
    for(int l = 10;~l;l--) {
        if(ans > n) break;
        memcpy(now,last,sizeof(now));
        for(int k = 1;k <= n;k++) {
            for(int i = 1;i <= n;i++) {
                for(int j = 1;j <= n;j++) {
                    now[i][j] = min(now[i][j],f[l][i][k] + last[k][j]);
                }
            }
        }
        int flag = 1;
        for(int i = 1;i <= n;i++) {
            if(now[i][i] < 0) {
                flag = 0;ss = 1;break;
            }
        }
        if(flag) {
            ans += (1 << l);
            for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) last[i][j] = now[i][j];
        }
    }
    if(ss) cout << ans + 1 << endl;
    else cout << "0" << endl;
}

[SCOI2016]萌萌哒

题意

在某些区间必须一样的情况下,可以组成多少个大数。

分析

这个区间必须一样我们可以考虑并查集来维护,但是我们合并并查集时就需要 的时间,这个必须优化,还是像 表,我们只需要维护 长度的所有区间就可以了,我们可以考虑一个区间拆除 个,然后不断递归下去,这样总复杂度看似为 的,但是考虑到只有 状态,而每一次递归势能都会减少,那么最后的复杂度为 了,那么最后就只需要考虑集合个数了。

代码

偷懒,用老师的代码了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int P = 30;
const int N = 550000 + 10;
const int mod = 1e9 + 7;

int n, m;
int logn[N], fa[N][P];

void in_it() {
    for (int p = 0; p < 19; p++)
        for (int i = 1; i <= n; i++) fa[i][p] = i;
    logn[1] = 0;
    for (int i = 2; i <= n; i++) logn[i] = logn[i >> 1] + 1;
}

int find(int i, int j) {
    if (fa[i][j] == i)
        return i;
    return fa[i][j] = find(fa[i][j], j);
}

void link(int x, int y, int k) {
    if (k < 0)
        return;
    int fx = find(x, k), fy = find(y, k);
    if (fx == fy)
        return;
    fa[fy][k] = fx;
    link(x, y, k - 1);
    link(x + (1 << k - 1), y + (1 << k - 1), k - 1);
}

int cnt = 0;
bool vis[N];

ll mpow(ll a, ll b) {
    ll rt = 1;
    for (rt; b; b >>= 1, a = a * a % mod) {
        if (b & 1)
            rt = rt * a % mod;
    }
    return rt;
}

int main() {
    //n = read(), m = read();
    cin>>n>>m;
    in_it();
    while (m--) {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        int k = logn[r1 - l1 + 1];
        link(l1, l2, k);
        link(r1 - (1 << k) + 1, r2 - (1 << k) + 1, k);
    }
    for (int i = 1; i <= n; i++) {
        int x = find(fa[i][0], 0);
        if (!vis[x])
            vis[x] = true, ++cnt;
    }
    ll ans;
    if (cnt == 1)
        ans = 10;
    else {
        ans = mpow(10, cnt - 1);
        ans = 1LL * ans * 9 % mod;
    }
    cout << ans << endl;
    return 0;
}