一种特殊的枚举算法

什么是倍增

顾名思义，即每一次翻倍增加。那么，这样我们就有了一种$O(logn)$阶的方法处理枚举方面的问题了。

一些题目

【倍增】luoguP1613 跑路

题目描述

小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图，小A家为点1，公司为点n，每条边长度均为一千米。小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

数据范围

50%的数据满足最优解路径长度<=1000；

100%的数据满足n<=50，m<=10000，最优解路径长度<=maxlongint。

题目分析

首先，显然这题是不能求最短路的跑路次数的。那么我们用bool类型的$f[i][j][t]$表示$i$到$j$存在长度为$2^t$的路径。

这样做可以使得$dis[i][j]$表示的是从$i$到$j$的最短跑路次数，因而最后用floyd求解最短路就好了。

参考：题解 P1613 【跑路】

 #include<bits/stdc++.h>

 const int maxn = ;

 bool f[maxn][maxn][];

 int dis[maxn][maxn];

 int n,m;

 int main()

 {

     scanf("%d%d",&n,&m);

     memset(dis, 0x3f3f3f3f, sizeof dis);

     for (int i=; i<=m; i++)

     {

         int x,y;

         scanf("%d%d",&x,&y);

         f[x][y][] = ;

         dis[x][y] = ;

     }

     for (int t=; t<=; t++)

         for (int k=; k<=n; k++)

             for (int i=; i<=n; i++)

                 for (int j=; j<=n; j++)

                     if (f[i][k][t-]&&f[k][j][t-]){

                         f[i][j][t] = ;

                         dis[i][j] = ;

                     }

     for (int k=; k<=n; k++)

         for (int i=; i<=n; i++)

             for (int j=; j<=n; j++)

                 if (dis[i][k]+dis[k][j] < dis[i][j])

                     dis[i][j] = dis[i][k]+dis[k][j];

     printf("%d\n",dis[][n]);

     return ;

 }

【LCA】luoguP3379 【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入输出格式

输入格式：

第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。

接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。

输出格式：

输出包含M行，每行包含一个正整数，依次为每一个询问的结果。

说明

时空限制：1000ms,128M

数据规模：

对于30%的数据：N<=10，M<=10

对于70%的数据：N<=10000，M<=10000

对于100%的数据：N<=500000，M<=500000

题目分析

呃这是一个裸的LCA题，那么就讲讲模拟法和倍增法吧（RMQ暂且不提）

模拟法

为了查询LCA(x,y)，我们从x开始一直向上染色。再从y开始一直向上查询，最先查询到的染色过的点就是LCA(x,y)。

有一个技巧，把染色的vis开成int数组，这样每一次就不用memset了（很慢的）

 #include<bits/stdc++.h>

 const int maxn = ;

 std::vector<int> f[maxn];

 int fa[maxn];

 int n,m,s;

 int vis[maxn];

 int read()

 {

     char ch = getchar();

     int num = ;

     for (; !isdigit(ch); ch = getchar());

     for (; isdigit(ch); ch = getchar())

         num = (num<<)+(num<<)+ch-;

     return num;

 }

 void buildStructure(int now)

 {

     for (unsigned int i=; i<f[now].size(); i++)

     if (!fa[f[now][i]])

     {

         fa[f[now][i]] = now;

         buildStructure(f[now][i]);

     }

 }

 int main()

 {

     n = read(), m = read(), s = read();

     for (int i=; i<n; i++)

     {

         int x = read(), y = read();

         f[x].push_back(y), f[y].push_back(x);

     }

     fa[s] = s;

     buildStructure(s);

     fa[s] = ;

     for (int i=; i<=m; i++)

     {

         int x = read(), y = read();

         for (; x; x = fa[x]) vis[x] = i;

         for (; y; y = fa[y])

             if (vis[y] == i)

                 break;

         printf("%d\n",y);

     }

     return ;

 }

当然以上做法是过不了这题的

倍增法

倍增的话，算是一种对于模拟法的优化吧。

我们每一次不止跳一步，而是以$2^i$步数向上跳。

那么就需要O(nlogn)预处理一些东西，查询则是O(logn)的。

参考：

1.【白话系列】最近公共祖先

2.LCA（离线Tarjan算法,在线倍增法）详解

3.LCA详解

4.题解 P3379 【【模板】最近公共祖先（LCA）】

 #include<bits/stdc++.h>

 const int maxn = ;

 const int logMaxn = ;

 int n,m,s;

 int deep[maxn],p[maxn][logMaxn];

 std::vector<int> f[maxn];

 inline int read()

 {

     char ch = getchar();

     int num = ;

     for (; !isdigit(ch); ch = getchar());

     for (; isdigit(ch); ch = getchar())

         num = (num<<)+(num<<)+ch-;

     return num;

 }

 void dfs(int now, int fa)　　　　　　　　　　//递归预处理

 {

     deep[now] = deep[fa]+;

     p[now][] = fa;

     for (int i=; (<<i)<=deep[now]; i++)

         p[now][i] = p[p[now][i-]][i-];

     for (unsigned int i=; i<f[now].size(); i++)

         if (f[now][i]!=fa)

             dfs(f[now][i], now);

 }

 int lca(int x, int y)　　　　　　　　　　　　//倍增LCA

 {

     if (deep[x] > deep[y]) std::swap(x, y);

     for (int i=logMaxn-; i>=; i--)

         if (deep[x]<=deep[y]-(<<i))

             y = p[y][i];

     if (x==y) return x;

     for (int i=logMaxn-; i>=; i--)

         if (p[x][i]==p[y][i])

             continue;

         else x = p[x][i], y = p[y][i];

     return p[x][];

 }

 int main()

 {

     n = read(), m = read(), s = read();

     register int i,x,y;

     for (i=; i<n; i++)

     {

         x = read(), y = read();

         f[x].push_back(y), f[y].push_back(x);

     }

     dfs(s, );

     for (i=; i<=m; i++)

     {

         x = read(), y = read();

         printf("%d\n",lca(x, y));

     }

     return ;

 }

【LCA】luoguP3398 仓鼠找sugar

题目描述

小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！

输入输出格式

输入格式：

第一行两个正整数n和q，表示这棵树节点的个数和询问的个数。

接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。

接下来q行，每行四个正整数a、b、c和d，表示节点编号，也就是一次询问，其意义如上。

输出格式：

对于每个询问，如果有公共点，输出大写字母“Y”；否则输出“N”。

说明

__本题时限1s，内存限制128M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。__

20%的数据 n<=200,q<=200

40%的数据 n<=2000,q<=2000

70%的数据 n<=50000,q<=50000

100%的数据 n<=100000,q<=100000

题目分析

题目大意就是判断树上(a,b)与(c,d)两条路径之间有没有交点。

看上去很唬人的样子对吧……

【待更】其实我也觉得很唬人

巴特西

初涉倍增&&LCA【在更】

什么是倍增

一些题目

【倍增】luoguP1613 跑路

题目描述

数据范围

题目分析

【LCA】luoguP3379 【模板】最近公共祖先（LCA）

题目描述

输入输出格式

说明

题目分析

模拟法

倍增法

【LCA】luoguP3398 仓鼠找sugar

题目描述

输入输出格式

说明

题目分析

最新文章

热门文章