相信大家初步了解了倍增之后,想要实践一下。这里选取了牛客的例题来讲解。来个👍 呗, 。
- 入门知识传送门
- 一些简单规定
- 指图上的最短路,在树上为 的简单路径。
- 指有根树上的深度。
[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; }