倍增专题
title: 倍增专题
categories:
- ICPC
tags:
- null
abbrlink: 2e8656b4
date: 2024-08-05 00:00:00
倍增大专题
[AHOI2008] 紧急集合 / 聚会 - 洛谷
题意:给定一棵树,多次查询费马点(bushi
费马点的含义是:到三个点的距离之和最小
Solution:考虑画图发现树上三点两两求lca,必然至少两个相同,然后我们只需要让费马点为另一个点就可以了,因为这一段路程只需要一个点走就最好了。
//考虑到让一个点走多的路程,两点走短路程
//首先对多种情况画图,可以知道树上三点两两求lca,必然至少两个相同
vector<int> e[N];
int fa[N],son[N],dep[N],siz[N];
int top[N];
void dfs1(int u,int f){ //搞fa,dep,son
fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;
for(int v:e[u]){
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v])son[u]=v;
}
}
void dfs2(int u,int t){ //搞top
top[u]=t; //记录链头
if(!son[u]) return; //无重儿子
dfs2(son[u],t); //搜重儿子
for(int v:e[u]){
if(v==fa[u]||v==son[u])continue;
dfs2(v,v); //搜轻儿子
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]])swap(u,v);
u=fa[top[u]];
}
return dep[u]<dep[v]?u:v;
}
int dis(int u,int v){
int mid=lca(u,v);
return dep[u]+dep[v]-2*dep[mid];
}
void solve(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
int c1=lca(x,y),c2=lca(x,z),c3=lca(y,z);
int c=c1^c2^c3;
int ans=dis(x,c)+dis(y,c)+dis(z,c);
cout<<c<<" "<<ans<<endl;
}
}
Codeforces Round 294 (Div. 2)E
题意:给定一棵树,多次查询。每次查询给出两点,求到两个点距离相等点的个数。
Solution:特殊情况,两个点重合,答案是n。再考虑无解情况,如果两个点的距离是奇数,则不存在这样的点,答案是0。最后考虑距离是偶数的点,不妨假设u深度大于v
- u与v高度不同,则找到中点,找到u的k-1级祖先,也就是中点的包含u的儿子的子树,记这个中点的儿子为son,以son为根的子树包含u。答案是sz[mid]-sz[u】
- u与v高度相等则两者lca上面的点可以对答案做贡献,考虑求出lca,求出son1,son表示lca的亲子节点,以son1为根的子树包含u,以son2为根的子树包含v。考虑答案是sz[lca]-sz[son1]-sz[son2] + n-sz[lca];
本题用倍增比较合适,可以对距离倍增快速利用get函数找到我们的k级祖先
struct edge{
int v,w;
};
//思考:要想知道一个数有几个二级制位,直接n=__lg(x)
//我们可以知道<n最近的2的次幂,9最大的是8,8虽然是2的3次方,但要遍历它的每一位
//需要3到0开始,也就是考虑到0的影响,我们可以正好满足偏移。
//2的3次方有四位,也就是__lg(x)就是我们需要的最高位,从它开始往低遍历
vector<edge>e[N];
const int len=__lg(N);
int dep[N];
int d[N];
int f[N][len+2];
int sz[N];
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
f[u][0]=fa;sz[u]=1;
for(int i=1;i<=len;i++)f[u][i]=f[f[u][i-1]][i-1];
//预处理倍增数组
for(auto [v,w]:e[u]){
if(v==fa)continue;
d[v]=d[u]+w;
dfs(v,u);
sz[u]+=sz[v];
}
}
int get(int x,int k) {//k级祖先
for(int i=len;i>=0;i--) if((k >> i) & 1) x = f[x][i];
return x;
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=len;i>=0;i--){
if(dep[f[x][i]]>=dep[y])x=f[x][i];
}
//跳到相同深度
if(x==y)return y;
//提提前判本身就是祖先关系
//cerr<<x<<" "<<y<<endl;
for(int i=len;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];y=f[y][i];
}
// cerr<<i<<" "<<x<<" "<<y<<endl;
}
//cerr<<x<<" "<<y<<endl;
//倍增一起向上跳,直到父亲就是答案
return f[x][0];
}
int dis(int u,int v){
return dep[u]+dep[v]-2*dep[lca(u,v)];
}
//lca的子树和去掉两个分支,本题需要求未知点祖先,无法使用树链跑分
void solve(){
cin>>n;//cin>>m;
for(int i=1;i<=n-1;i++){
int u,v;cin>>u>>v;
e[u].push_back({v,1});
e[v].push_back({u,1});
}
dfs(1,0);
//for(int i=1;i<=n;i++)cerr<<sz[i]<<" ";
//cerr<<endl;
cin>>m;
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;int mid=lca(u,v);
// cerr<<mid<<endl;
if(dep[u]<dep[v])swap(u,v);
int ans=0;
if(u==v)ans=n;
else {
int dist=dis(u,v);
if(dist%2)ans=0;
else {
if(dep[u]==dep[v]){
int k=dep[u]-dep[mid]-1;
int s1=get(u,k),s2=get(v,k);
ans=n-sz[s1]-sz[s2];
}
else {
int k=dist/2-1;
int s1=get(u,k);int s2=get(u,k+1);
ans=sz[s2]-sz[s1];
}
}
}
cout<<ans<<endl;
}
}
Minimum spanning tree for each edge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
Cut - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
校赛亚轴(板子复习
http://oj.daimayuan.top/problem/805最小瓶颈生成树
注意倍增到最后两边都还要再挑一条边
题目:给定一张 n 个点 m 条边的无向图,每条边有一个权值,定义瓶颈路权值为某一条从点 i 到 j 的路径上的最大权值,有 q个询问,每次询问给出两个点 (s,t),求从 s 到 t 的最小瓶颈路权值
Sol:先求最小生成树。然后求两点路径的最大边权值
int a[N];
struct edge{
int v;
int w;
};
vector<edge>e[N];
const int len=__lg(N);
int dep[N];
//int d[N];
int f[N][len+2];//数组多开
int ans[N][len+2];
struct edges{
int u,v,w;
bool operator<(const edges &t)const
{return w < t.w;}
}ff[M];//结构体存边
struct DSU {
vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
void add(int u,int v,int w){
e[u].push_back({v,w});
}
int cnt=0,tmp=0;
bool kruskal(){//返回的是原图的连通性,最小生成树的答案并没有返回,注意自己处理。
sort(ff+1,ff+m+1);
DSU dsu(n+1);
int cnt=0;
for(int i=1; i<=m; i++){
int x=(ff[i].u);
int y=(ff[i].v);
if(!dsu.same(x,y))
{
dsu.merge(x,y);
add(ff[i].u,ff[i].v,ff[i].w);
add(ff[i].v,ff[i].u,ff[i].w);
tmp+=ff[i].w;
cnt++;
}
}
return cnt==n-1;
}
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
f[u][0]=fa;
for(int i=1;i<=len;i++){
f[u][i]=f[f[u][i-1]][i-1];
ans[u][i]=max(ans[u][i-1],ans[f[u][i-1]][i-1]);
//预处理倍增数组
}
for(auto [v,w]:e[u]){//加边权后增加参数w
if(v==fa)continue;
// d[v]=d[u]+w;
ans[v][0]=w;
dfs(v,u);
//sz[u]+=sz[v];
}
}
int lca(int x,int y){
int res=0;
if(dep[x]<dep[y])swap(x,y);
// cerr<<x<<" "<<y<<endl;
// bug(res);
for(int i=len;i>=0;i--){
if(dep[f[x][i]]>=dep[y]){res=max(res,ans[x][i]);x=f[x][i];}
}
//跳到相同深度
//cerr<<x<<endl;
if(x==y)return res;
//提提前判本身就是祖先关系
for(int i=len;i>=0;i--){
if(f[x][i]!=f[y][i]){
res=max(res,ans[x][i]);
res=max(res,ans[y][i]);
x=f[x][i];y=f[y][i];
}
}
//倍增一起向上跳,直到父亲就是答案
res=max(res,ans[y][0]);
return max(res,ans[x][0]);
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v,w;cin>>u>>v>>w;
ff[i]={u,v,w};
}
kruskal();
// cerr<<tmp<<endl;
dfs(1,0);
// bug(ans[1][0]);
// bug(ans[2][0]);
int q;cin>>q;
for(int i=1;i<=q;i++){
int u,v;cin>>u>>v;
cout<<lca(u,v)<<endl;
}
}
https://www.luogu.com.cn/problem/CF1516D给你一个 $n$ 个数的序列 $a_i$,和 $q$ 次询问,每次询问一段区间 $[l,r]$,问至少要把这个区间分为几个子区间,才能使得每个子区间内的数的乘积等于这个子区间内所有数的 $LCM$ 。
$n,a_i,q\le 10^5$
Sol:先考虑固定L的情况,下一个端点在哪,由于lcm随集合大小单调性和质因数的限制我们可以得到。但最坏我们可能每次只能一步一步跳,所以我们倍增跳,在不超过的边界的情况下跳,最后再跳一步。
int a[N];
int f[N][21];
int v[N];
vector<int>c[N];
bool st[N];
void init(int mm){
for(int i=2;i<=mm;i++){
if(st[i])continue;
// bug(i);
c[i].push_back(i);
for(int j=i+i;j<=mm;j+=i){
st[j]=true;
c[j].push_back(i);
}
}
}
void solve(){
int q;
cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
f[n+1][0]=n+1;
memset(v,0x3f,sizeof v);
for(int i=n;i>=1;i--){
f[i][0]=f[i+1][0];
for(auto j:c[a[i]]){
f[i][0]=min(f[i][0],v[j]);
v[j]=i;
}
}
for(int i=1;i<=20;i++){
for(int j=1;j<=n;j++){
if(f[j][i-1]<=n)f[j][i]=f[f[j][i-1]][i-1];
else f[j][i]=n+1;
}
}
while(q--){
int l,r;cin>>l>>r;
int ans=0;
for(int i=20;i>=0;i--){
if(f[l][i]<=r){
ans+=(1<<i);
l=f[l][i];
}
}
ans++;
cout<<ans<<endl;
}
}
对于边带权的有向图 𝐺=(𝑉,𝐸),请找出一个点数最小的环,使得环上的边权和为负数。保证图中不包含重边和自环。
Sol:不能直接dp,我们考虑利用倍增转移加速。
int n, m;
int f[9][301][301],v[301][301],g[301][301];
//f[k][i][j]:从i到j恰好走k步的边权和最小值
void solve(){
cin>>n>>m;
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 x,y,z;cin>>x>>y>>z;
f[0][x][y]=z;
}
for(int i=1;i<=8;i++){
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
for(int z=1;z<=n;z++){
if(f[i-1][x][z]<inf&&f[i-1][z][y]<inf){
f[i][x][y]=min(f[i][x][y],f[i-1][x][z]+f[i-1][z][y]);
}
}
}
}
}
int ans=0;
memset(v,0x3f,sizeof v);
for(int i=1;i<=n;i++)v[i][i]=0;
for(int i=8;i>=0;i--){
memset(g,0x3f ,sizeof g);
for(int x=1;x<=n;x++){
for(int y=1;y<=n;y++){
for(int z=1;z<=n;z++){
if(v[x][z]<inf&&f[i][z][y]<inf){
g[x][y]=min(g[x][y],v[x][z]+f[i][z][y]);
}
}
}
}
bool ok=true;
for(int j=1;j<=n&&ok;j++){
if(g[j][j]<0)ok=false;
}
if(ok){
ans+=(1<<i);
memcpy(v,g,sizeof g);
}
}
ans++;
if(ans>n)cout<<0<<endl;
else cout<<ans<<endl;
}
题意:给定一张由 $T$ 条边构成的无向图,点的编号为 $1 \sim 1000$ 之间的整数。 求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边(可以重复经过)的最短路。
一道不错广义矩阵乘法的矩阵快速幂
debug:1.起点终点也要换成映射后的值 2。注意边的信息输入顺序,不是所有题都默认
// Problem: 牛站
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/347/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define debug1(x) cerr<<x<<" "
#define debug2(x) cerr<<x<<endl
const int N = 2e2 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
int g[N][N];
int res[N][N];
//对floyd新的认识:一条边一条边考虑,且会连续更新,这对边数没有限制
map<int,int>mp;
int k,s,e;
//注意到:需要走1e6条边,但只有100条边,1000点,这时候往往和数学有关
//最后只有200个点用到,所以为了降低常数,我们选择离散化,并且题目本身
//给出的数据就是随机落在1-1000
//将 temp 数组声明为 static 的意义在于使得 temp 变量在函数调用结束后
//仍然保留其数值,
//而不会被销毁。
void mul(int c[][N],int a[][N],int b[][N]){
static int tmp[N][N];
memset(tmp,0x3f ,sizeof tmp);
for (int k = 1; k <= n; k ++ )//注意枚举顺序
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
tmp[i][j] = min(tmp[i][j], a[i][k] + b[k][j]);
memcpy(c, tmp, sizeof tmp);
}
//每做一次,表示res经过a条边,g经过2^k条边,那么得到的res就是经过a+2^k条的
//边的距离
void qmt(){
memset(res,0x3f ,sizeof res);
for(int i=1;i<=n;i++)res[i][i]=0;
//res初始化,o条边的时候,到达自己位0,无法到达别人,记为正无穷
while(k){
if(k&1)mul(res,res,g);
mul(g,g,g);
k>>=1;
}
}
void solve(){
cin>>k>>m>>s>>e;
memset(g,0x3f ,sizeof res);
if(!mp.count(s))mp[s]=++n;
if(!mp.count(e))mp[e]=++n;
s=mp[s];
e=mp[e];
for(int i=1;i<=m;i++){
int u,v,w;
//注意信息顺序
cin>>w>>u>>v;
// cerr<<u<<" "<<v<<" "<<w<<endl;
if(!mp.count(u))mp[u]=++n;
if(!mp.count(v))mp[v]=++n;
u=mp[u];v=mp[v];
//cerr<<u<<" "<<v<<" "<<w<<endl;
g[u][v]=g[v][u]=min(g[u][v],w);
}
qmt();
cout<<res[s][e]<<endl;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
//cin>>t;
t=1;
while (t--) {
solve();
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!