蓝桥杯 Day7 java组倍增

2021-07-05 23:38:02

倍增法和二分法是“相反”的算法。二分是每次缩小一倍，从而以 O(logn)的步骤极快地缩小定位到解；倍增是每次扩大一倍，从而以 O(2^n)的速度极快地扩展到极大的空间。所以倍增和二分的效率都很高。

二分法与倍增的应用场景

二分法是缩小区间，最后定位到一个极小的区间，小到这个区间的左右端点重合（或者几乎重合），从而得到解，解就是最后这个极小区间的值。所以二分法的适用场合，是在一个有序的序列，或者一个有序的曲线上，通过二分缩小查询区间，其目的是找到一个特定的数值。
倍增相反，是从小区间扩大到大区间。在区间问题中，它是在大区间上求解和区间查询有关的问题，例如区间最大值或最小值。这种应用例如RMQ问题，是用基于倍增的ST算法解决。
不过，除了在区间上的应用，倍增也能用于数值的精确计算。如果空间内的元素满足倍增关系，或者能利用倍增关系来计算，那么也能用倍增法达到求解这些元素的精确值的目的。这种应用有快速幂、LCA（最近公共祖先）等。

ST 算法

ST 算法是求解 RMQ 问题的优秀算法，它适用于静态空间的 RMQ 查询。
静态空间的 RMQ 问题（Range Minimum/Maximum Query，区间最值问题）：给定长度为 n 的静态数列，做 m 次询问，每次给定 L,R≤n，查询区间[L, R]内的最值。下面以区间最小值问题为例。
用暴力搜区间 [L,R] 的最小值，即逐一比较区间内的每个数，复杂度是O(n) 的；m 次查询，复杂度 O(mn)。暴力法的效率很低。
ST 算法的基本思路，包括两个步骤：1.把整个数列分为很多小区间，并提前计算出每个小区间的最值；2.对任意一个区间最值查询，找到覆盖它的两个小区间，用两个小区间的最值算出答案。

倍增的实现

1. 把数列按倍增分成小区间

对数列的每个元素，把从它开始的数列分成长度为1、2、4、8、…的小区间。

第 1 组是长度为 1 的小区间，有 n 个小区间，每个小区间有 1 个元素；
第 2 组是长度为 2 的小区间，有 n 个小区间，每个小区间有 2 个元素；
第 3 组是长度为 4 的小区间，有 n 个小区间，每个小区间有 4 个元素；
共有logn 组。

每组的小区间的最值，可以从前一组递推而来。
定义 dp[s][k]，表示左端点是 s，区间长度为 2^k 的区间最值。它的递推关系是：（1<<(k-1)等于 2^{k-1}）
dp[s][k]=min（dp[s][k−1],dp[s+1<<(k−1)][k−1]）
图中的每一组都需计算 n 次，共 logn 组，总计算量是 O(nlogn)。

2. 查询任意区间的最值

查询一个任意区间 [L, R]的最小值，就是找到以 L 为起点的区间（区间终点小于 R），和以 R 为终点的区间（起点大于 L），这些区间的交集，就是 [L, R]。
而上面的分区方法，有以下结论：以任意元素为起点，有长度为 1、2、4、…的小区；以任意元素为终点，它前面也有长度为 1、2、4、…的小区。再根据这个结论，可以把需要查询的区间 [L, R] 分为 2 个小区间，且这两个小区间属于同一个组：以 L 为起点的小区间、以 R 为终点的小区间，让这两个小区间首尾相接覆盖 [L,R]，区间最值从两个小区间的最值求得。一次查询的计算复杂度是 O(1)。
最后给出区间 [L, R] 最小值的计算公式，等于覆盖它的两个小区间的最小值：
min(dp[L][k],dp[R−(1<<k)+1][k]);

第一题区间最大值

输入输出样例

示例 1

输入

输出

import java.util.Scanner;

public class Main {
    private static int N = 0;
    private static int Q;
    private static int[] a = new int[500005];
    private static int[][] dp = new int[1000][50];//随便设的大小

    public static void init() {
        for (int i = 1; i <= N; i++) {
            dp[i][0] = a[i];//小区间长度为1，最小值即为本身
        }
        double p = Math.log(N) / Math.log(2);//java里只能这么求对数 还必须用double来接？
        for (int i = 1; i <= (int) p; i++) {
            for (int j = 1; j + Math.pow(2, i) <= N + 1; j++) {
                dp[j][i] = Math.max(dp[j][i - 1], dp[j + (int) Math.pow(2, i - 1)][i - 1]);
            }
        }
    }

    public static int fun_1(int L, int R) {
        double ans = Math.log(R - L + 1) / Math.log(2);
        return Math.max(dp[L][(int) ans], dp[R - (int) Math.pow(2, (int) ans) + 1][(int) ans]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        Q = scanner.nextInt();
        for (int i = 1; i <= N; i++) {
            a[i] = scanner.nextInt();
        }
        init();//初始化dp数组
        int L, R;
        for (int i = 1; i <= Q; i++) {
            L = scanner.nextInt();
            R = scanner.nextInt();
            System.out.println(fun_1(L, R));
        }
    }
}

第二题 m计划

和第一题差不多 min改为max

样例输入

5 3
5 3 2 4 1

样例输出

2
2
1

import java.util.Scanner;

public class Main {
    private static int N = 0;
    private static int M;
    private static int[] a = new int[500005];
    private static int[][] dp = new int[1000][50];//随便设的大小

    public static void init() {
        for (int i = 1; i <= N; i++) {
            dp[i][0] = a[i];//小区间长度为1，最小值即为本身
        }
        double p = Math.log(N) / Math.log(2);//java里只能这么求对数 还必须用double来接？
        for (int i = 1; i <= (int) p; i++) {
            for (int j = 1; j + Math.pow(2, i) <= N + 1; j++) {
                dp[j][i] = Math.min(dp[j][i - 1], dp[j + (int) Math.pow(2, i - 1)][i - 1]);
            }
        }
    }

    public static int fun_1(int L, int R) {
        double ans = Math.log(R - L + 1) / Math.log(2);
        return Math.min(dp[L][(int) ans], dp[R - (int) Math.pow(2, (int) ans) + 1][(int) ans]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        for (int i = 1; i <= N; i++) {
            a[i] = scanner.nextInt();
        }
        init();//初始化dp数组
        for (int i = 1; i <= N-M+1; i++) {
            System.out.println(fun_1(i,i+M-1));
        }
        return;
    }
}

真恶心啊

码农公寓