倍增按照字面意思就是翻倍。1->2->4->8…,具体到实际的问题包括区间极值查询RMQ,最近公共祖先LCA。

 比如在查找第7个数,第1个不够,第2个不够,第4个不够,第8个超过,则在4-8之间进行查找即可,则可以将时间复杂度由O(n)降为O(logn)。

 不过这些例子都是倍增思想的体现,并不是说明倍增一定要按照这些例子来,比如说我们一般会使用2^k作为倍增中使用的倍增因子(我暂且这么叫它),根据不同题目也可以设计不同的底数如3,4等。下面给一些具体的题目例子。

洛谷P2880

 题目链接:https://www.luogu.com.cn/problem/P2880

 此题是典型的区间极值查询问题,分别求出区间的极大值和极小值,对于查询区间进行相减即得到最终结果。附上代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int maxn = 5e4 + 3;
int maxx[maxn][32], mini[maxn][32];
int RMQ(int l, int r)
{
    int k = floor(log2(r-l+1));
    return max(maxx[l][k], maxx[r-(1<<k)+1][k]) - min(mini[l][k], mini[r-(1<<k)+1][k]);
}
int main()
{
    int n, m;
    int t;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &t);
        maxx[i][0] = t;
        mini[i][0] = t;
    }
    for (int k = 1; 1<<k <= n; k++)
        for (int i = 1; i+(1<<k)-1 <= n; i++)
        {
            maxx[i][k] = max(maxx[i][k-1], maxx[i+(1<<k-1)][k-1]);
            mini[i][k] = min(mini[i][k-1], mini[i+(1<<k-1)][k-1]);
        }
    for (int i = 0; i < m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", RMQ(l, r));
    }
    return 0;
}

洛谷P1613

 题目链接:https://www.luogu.com.cn/problem/P1613

 本题结合倍增最短路,考虑到题目中2^k的特殊条件,可以想到使用倍增。因为距离为2^k时,可以一步到达,所以我们将所有距离为2^k的点之间的距离都设置为1,而这就可以用到倍增来完成。之后利用floyd算法完成最短路的计算即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
// 倍增+最短路,若两点间距离是2^k,则认为两点之间的距离为
const int maxn = 50 + 3;
const int maxm = 20 + 2;
bool flag[maxn][maxn][maxm];
int dis[maxn][maxn];
int main()
{
    int n, m;
    int x, y;
    scanf("%d%d", &n, &m);
    memset(dis, 0x3f3f3f3f, sizeof dis);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &x, &y);
        flag[x][y][0] = true;
        dis[x][y] = 1;
    }
    for (int k = 0; k < 20; k++)
        for (int t = 1; t <= n; t++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                {
                    if (flag[i][t][k] && flag[t][j][k])
                    {
                        flag[i][j][k+1] = true;
                        dis[i][j] = 1;
                    }
                }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <=n; j++)
                if (dis[i][k]+dis[k][j] < dis[i][j])
                    dis[i][j] = dis[i][k] + dis[k][j];
    cout << dis[1][n];
    return 0;
}
分类: 算法

0 条评论

发表评论