P1890 题解

· · 个人记录

题面

题面分析

这道题很明显可以用数学的方法强力解决，但是在这里

我给大家推荐一种更好的短小精悍的数据结构 —— st表

方法介绍

有效的数据结构，$st$表一般由一个二维数组存储 #### 举个栗子： 假设我们要求多个区间中的最大值，并且查询次数非常多 那么我们令 $f[i][j]$的意义为从第$i$个数开始向后$2$的$j$次方个数之间的最大值 这里考虑到数据范围，所以数组的第二维仅仅开到$31$就可以了 接着，我们需要处理的是状态转移方程，下面我给大家画一张解释图片： ![](https://s1.ax1x.com/2022/04/03/q7iJSg.png) 很明显，假如我们需要求出一个区间内的最大值 我们就需要把这个区间砍成两半，也就是$l$到$l+2^j$,和$l+2^j+1$到$l+2^j+1+2^j

也就是说左端点后2^j个数内的最大值与l+2^j+1再后2^j个数的最大值比出的最大值

根据我们刚才状态定义的解释，我们就可以得到状态转移方程：

f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);

这是st表的预处理部分，我们可以得到：

for (int j = 1; j <= 30; j++) { //一定先枚举j
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
        f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); //方程
    }
}

经过log级别的预处理后，我们查询的时间复杂度就仅仅是O(1)了

例题处理

对于这道题，和st表模板相差不大，仅仅是将区间最大值改成了区间的最大公约数，在基础模板上改动不大， 背好模板套代码即可

Code

#include <bits/stdc++.h>
#define maxn 10005
using namespace std;
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}
int n, m, f[maxn][31];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &f[i][0]);
    }
    for (int j = 1; j <= 30; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);//预处理
        }
    }
    for (int i = 1, l, r, k; i <= m; i++) {
        scanf("%d %d", &l, &r);
        k = log2(r - l + 1);//得到区间长度
        printf("%d\n", gcd(f[l][k], f[r - (1 << k) + 1][k]));//查询
    }
}