python

9.0 KiB

Raw Permalink Blame History Unescape Escape

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 1273. 天才的记忆

一、题目描述

从前有个人名叫 WNB，他有着天才般的记忆力，他珍藏了许多许多的宝藏。

在他离世之后留给后人一个难题（专门考验记忆力的啊！），如果谁能轻松回答出这个问题，便可以继承他的宝藏。

题目是这样的：给你一大串数字（编号为 1 到 N，大小可不一定哦！），在你看过一遍之后，它便消失在你面前，随后问题就出现了，给你 M 个询问，每次询问就给你两个数字 A,B，要求你瞬间就说出属于 A 到 B 这段区间内的最大数。

一天，一位美丽的姐姐从天上飞过，看到这个问题，感到很有意思（主要是据说那个宝藏里面藏着一种美容水，喝了可以让这美丽的姐姐更加迷人），于是她就竭尽全力想解决这个问题。

但是，她每次都以失败告终，因为这数字的个数是在太多了！

于是她请天才的你帮他解决。如果你帮她解决了这个问题，可是会得到很多甜头的哦！

输入格式 第一行一个整数 N 表示数字的个数。

接下来一行为 N 个数，表示数字序列。

第三行读入一个 M，表示你看完那串数后需要被提问的次数。

接下来 M 行，每行都有两个整数 A,B。

输出格式 输出共 M 行，每行输出一个数，表示对一个问题的回答。

数据范围 1≤N≤2×10^5,1≤M≤10^4,1≤A≤B≤N。

输入样例：

6
34 1 8 123 3 2
4
1 2
1 5
3 4
2 3

输出样例：

二、`RMQ`问题

询问某个区间内的最大或最小值,一般采用ST算法，也称ST表、跳表。

缺陷：离线算法，不能修改，否则需要用到线段树

暴力解法

容易想到的是遍历，查询一次的复杂度是O(n)。但当数据量非常大且查询很频繁时，该算法无法在有效的时间内查询出正解,多次时的复杂度是O(N*M)

`ST`算法

1、预处理

状态表示 设a[i]是要求区间最值的数列，f[i][j]表示 从第i个数起连续2^j个数中的最大值

举栗子： a数列为：\large 3　 2　 4　 5　 6　 8　 1　 2　 9　 7　

f[1,0]表示第1个数起，长度为2^0=1的最大值，其实就是3这个数。 f[1,1] = max(3,2) = 3 f[1,2]=max(3,2,4,5) = 5 f[1,3] = max(3,2,4,5,6,8,1,2) = 8;

初始值 可以容易的看出f[i,0]就等于a[i]。（dp的初始值）

状态转移

Q:为什么j是外循环而i是内循环? 能不能调换一下嘞？答案是 不可以,这个类似于区间DP，需要先枚举长度。

你可以这样来理解：动态规划体现在二维数组形式上，就是一个二维填表的过程，可能采用的顺序是：

从左到右，从上到下去填写
从上到下，从左到右去填写
从右下角向左上角去填写
....

具体该怎么填写，其实是和实际场景相关的，必须 保证无后效性，就是这块填写完了就是填写完了，不能一会用到时说还没有填写，那就彼此依赖不上了。本题如果按列填写，就是j依赖于j-1,也就是按列，可以完成任务。如果是按行，你会发现i是东一下，西一下，跳来跳去，整不好就在下一个要用到前序数字时，它还没有完成填充，这样彼此就无法实现依赖了！因此需要先枚举j，再枚举i。

查询

如何确定k呢？

对于每个查询 [l,r]，需要先找出最大的一个满足 \large 2^k<len 的 \large k，其中 len=r−l+1，方法就是两边求对数：

\large log_2{2^k}<log_2(len)  \\
\Rightarrow \\
k<log_2(len)

k要想取最大的整数，就是(int)(log_2(len)) 如果是给整数赋值，就不用写强制转换，故直接写成：

int k = log2(len);

构造交集 查询时通过构建2^k的方法，造成\large [a,a+2^k-1]与\large [b-2^k+1,b]存在一个交集，分别求f(a,k)与f(b-2^k+1,k)，然后取一个max就是答案，虽然这里有一部分是重复的，但求最大值不怕重复！同时，也因为这个原因，使得st算法，也就只能用来计算最大最小值，不能用来处理其它需求。　

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];

// 预处理
void rmq() {
    for (int j = 0; j < M; j++)                     // 注意是j在外层,类似于区间DP,长度在外层
        for (int i = 1; i + (1 << j) - 1 <= n; i++) // i(行)在内层
            if (j == 0)                             // base case 边界值
                f[i][j] = w[i];
            else
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

// 查询区间最大值
int query(int l, int r) {
    int len = r - l + 1;
    int k = log2(len);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];

    rmq(); // ST表初始化

    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        printf("%d\n", query(l, r));
    }
    return 0;
}

四、练习题

最大、最小一起来

思路这一题是需要用到最大值和最小值两个RMQ，求出来后再相减就是答案。

#include <bits/stdc++.h>
using namespace std;

const int N = 200010, M = 20;
int w[N];             // 原始数组
int f[N][M], g[N][M]; // 最大值结果数组，最小值结果数组

int n, q;
/*
输入样例：
6 3
1 7 3 4 2 5
1 5
4 6
2 2

答案：
6
3
0
*/
// 预处理最大值
void rmqMax() {
    for (int j = 0; j < M; j++)                     // 注意是j在外层,类似于区间DP,长度在外层
        for (int i = 1; i + (1 << j) - 1 <= n; i++) // i(行)在内层
            if (j == 0)                             // base case 边界值
                f[i][j] = w[i];
            else
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
// 查询区间最大值
int queryMax(int l, int r) {
    int len = r - l + 1;
    int k = log2(len);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

// 预处理最小值
void rmqMin() {
    for (int j = 0; j < M; j++)                     // 注意是j在外层,类似于区间DP,长度在外层
        for (int i = 1; i + (1 << j) - 1 <= n; i++) // i(行)在内层
            if (j == 0)                             // base case 边界值
                g[i][j] = w[i];
            else
                g[i][j] = min(g[i][j - 1], g[i + (1 << j - 1)][j - 1]);
}

// 查询区间最小值
int queryMin(int l, int r) {
    int len = r - l + 1;
    int k = log2(len);
    return min(g[l][k], g[r - (1 << k) + 1][k]);
}

int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q;

    for (int i = 1; i <= n; i++) cin >> w[i];

    rmqMax(); // ST表初始化
    rmqMin(); // ST表初始化

    while (q--) {
        int l, r;
        cin >> l >> r;
        printf("%d\n", queryMax(l, r) - queryMin(l, r));
    }
    return 0;
}

最大公约数

这一题跟上一题差不多，只需将max()改成\_\_gcd()就行了。

#include <bits/stdc++.h>

using namespace std;
const int N = 200010, M = 18;
/*
输入样例：
5 3
4 12 3 6 7
1 3
2 3
5 5

答案：
1
3
7
*/
int n, q;
int w[N];
int f[N][M];
// 预处理
void rmq() {
    for (int j = 0; j < M; j++)                     // 注意是j在外层,类似于区间DP,长度在外层
        for (int i = 1; i + (1 << j) - 1 <= n; i++) // i(行)在内层
            if (j == 0)                             // base case 边界值
                f[i][j] = w[i];
            else
                f[i][j] = __gcd(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

// 查询区间最大值
int query(int l, int r) {
    int len = r - l + 1;
    int k = log2(len);
    return __gcd(f[l][k], f[r - (1 << k) + 1][k]);
}
int main() {
    // 加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> w[i];
    rmq();
    while (q--) {
        int l, r;
        cin >> l >> r;
        printf("%d\n", query(l, r));
    }
    return 0;
}

9.0 KiB Raw Permalink Blame History Unescape Escape