2020-11-27 15:15 已编辑天津大学

关注

倍增例题

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

入门知识传送门
一些简单规定
- $dis(x,y)$ 指图上的最短路，在树上为 $x,y$ 的简单路径。
- $dep(x,y)$ 指有根树上的深度。

[AHOI2008]MEET 紧急集合

题意

给出三个点 $x,y,z$ ，找到一个节点 $p$ 使 $dis(p,x)+dis(p,y)+dis(p,z)$ 最小。

分析

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

令 $A=lca(x,y)$ 如果 $lca(x,z) \ne A$ ，那么由于 $A$ 在 $path(x,y)$ 上，则 $lca(x,z)$ 必然是 $A$ 的祖先，或者子树。那么等同于 $lca(z,y)=lca(x,z)$ ，或者 $lca(z,y) = lca(y,x)$ 。
那么容易得到 $x,y,z$ 两两求出 $lca$ 那么必然存在两个 $lca$ 是相同的，那么另一个 $lca$ 就是最优答案，那么剩下的就是树上距离公式了 $dis(x,y) = dis(root,x)+dis(root,y)-2\times dis(root,lca(x,y))$ 。考虑倍增求 $lca$ ，那么总的复杂度为 $O(n\log n + Q\log n)$ 。

代码

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

疫情控制

题意

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

分析

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

贪心，我们可以容易想到，由于可以同时调动，那么对于任意一支军队，都要使他尽量的往上，因为这样不会使答案更劣，但是这里我们并不能慢慢跳父亲，而且考虑倍增，考虑的方式可以类比倍增求 $lca$ 的过程，而且同时保存 $dis(fa_{2^p},x)$ 的答案。
我们做完上一步，现在发现，军队被划分成两种。
- 可以到达 $1$ 号节点。
- 不可以到达 $1$ 号节点。
那么我们先对所有子树遍历，考虑这个子树是否可以不需要军队了。那么最后我们剩下的就是，一些还需要军队来出现的子树和一些搁置在 $1$ 号节点的军队。对于每个子树我们记录它的根节点到 $1$ 的距离为 $B$ ，和每一支可以到达 $1$ 号节点还剩余的时间 $A$ 。那么现在问题转化为。是否可以在 $A$ 序列中选取 $|B|$ 个元素，使 $\forall i$ 满足 $A_i \ge B_i$ 。这个可以考虑贪心，将 $A_i$ 和 $B_i$ 都从小到大排序，维护两个指针 $P_a,P_b$ 。
- 如果 $P_a$ 的子树需要一个军队，那么我们可以考虑不让 $P_a$ 跳到 $1$ 号节点，直接使 $P_a$ 的子树变为已覆盖，因为每一个没有被覆盖的子树至少需要一个军队到覆盖，那么在 $B_{P_a}$ 还没有被访问时覆盖，这样一定可以使答案不更劣。
- 如果 $P_a \ge P_b$ 直接覆盖，考虑下一个 $P_a$ 和 $P_b$ 。
- 如果 $P_a < P_b$ ，考虑下一个 $P_a$ 。

最后判断所有子树都被覆盖就可以了，这样总的复杂度为 $O(m\log w \log m)$ 。

代码

#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

题意

给你俩个节点 $A,B$ 和一棵无根树，找出树上满足 $dis(x,A)=dis(x,B)$ 的节点个数。

分析

我们比较好思考的就是 $path(A,B)$ 至多只有一个合法点，而且这个合法点一定是满足 $dis(x,A)=\frac{1}{2} dis(A,B)$ 的，所以当 $dis(A,B) \bmod 2 = 1$ 时是一定无解的。那么我们现在考虑 $x\in path(A,B)$ 的节点位置，比较好分析的是 $path(A,B)$ 只会在 $lca(A,B)$ 处发生一次转折，所以 $x$ 是 $A,B$ 中深度较深的祖先，具体来讲是它的 $\frac{dis(A,B)}{2}$ 级祖先 $P$ 。现在只需要讨论 $lca$ 和 $P$ 的关系就好了。

$P = lca$ 那么要使 $dis(x,A)=dis(x,B)$ ，那么可以选择的节点就是，所有的节点除去以 $lca$ 为根的， $A,B$ 所在的两个子树的所有节点。
$P \ne lca$ 那么要使 $dis(x,A)=dis(x,B)$ ，那么可以选择的节点就是，以祖先 $P$ 为根的子树中，除去深度较深的 $A,B$ 所处的子树节点。

那么总的复杂度为 $O(n\log n)$ ，因为我们需要查找 $K$ 级祖先和查找 $lca$ 。

代码

#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]国旗计划

题意

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

分析

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

代码

#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

题意

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

分析

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

代码

#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]萌萌哒

题意

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

分析

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

代码

偷懒，用老师的代码了。

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