UVALive 6582 Magical GCD(数学+数据结构)解题报告

2017-02-20 255 次浏览 解题报告

Also available: UVALive 6582, UVA 1642, Gym 100299C

题意

给定一个序列,定义一个连续子序列的 Magical GCD 为子序列内所有元素的 GCD 乘上区间长度,求最大的 Magical GCD。

解题思路

首先我们可以想到枚举区间右端点,对于每一个右端点,向左遍历来不断更新最大值,不过这样的时间复杂度会到 $O(n^{2})$,对于这道题是撑不住的,因此我们需要想办法在每次枚举右端点时,降低遍历左端点时的时间复杂度。

我们可以注意到,在确定右端点的所有区间内,随着区间长度不断增大,GCD 只会保持不变或者减小,且如果减小,新的 GCD 最大为原来的 1/2(当从因子中拿出的数最小,新 GCD 最大,拿出的最小为 2)。由此可知,对于区间内最大数值 m,不同 GCD 的个数最大为 $\log_2 m$,这样我们每次只需要遍历所有不同的 GCD,复杂度降低到 $O(n\log m)$。对于相同的 GCD,我们只需要记录最左端的一个即可(为了取最大长度)。

因此,本题的做法就很清楚了,只需要枚举右端点,然后维护一个记录不同 GCD 及其最左端位置的数据结构并不断更新答案即可。

示例解释(i 为枚举的右端点,括号内为维护的不同 GCD 值及其最左端位置):

i = 0
(30, 0)

i = 1
(30, 0)
(60, 1)

i = 2
(10, 0)
(20, 1)

i = 3
(10, 0)
(20, 1)

i = 4
(10, 0)
(20, 1)

参考代码

#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

long long GCD(long long a, long long b) {
    return b ? GCD(b, a%b) : a;
}

int main(int argc, char const *argv[]) {
    int t, n;
    long long a[100000];
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i=0; i<n; ++i) {
            scanf("%lld", &a[i]);
        }
        long long ans = a[0];
        stack<pair<long long, int> > s; // 维护不同 GCD 的值及其最左端位置
        s.push(make_pair(a[0], 0));
        for(int i=1; i<n; ++i) {
            vector<pair<long long, int> > v;
            v.push_back(make_pair(a[i], i));
            while(!s.empty()) {
                v.push_back(make_pair(GCD(s.top().first, a[i]), s.top().second)); // 获得栈顶的 GCD 并计算新的 GCD,暂存到 v 中
                s.pop();
            }
            for(int j=1; j<v.size(); ++j) { // 去除重复的 GCD 值
                if(v[j].first == v[j-1].first)
                    v.erase(v.begin()+(j--)-1);
            }
            for(int j=v.size()-1; j>=0; --j) { // 将新的一组不同 GCD 值重新放回栈内并更新答案
                ans = max(ans, v[j].first*(i-v[j].second+1));
                s.push(v[j]);
            }
        }
        printf("%lld\n", ans);
    }
    
    return 0;
}

bLue 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
本文地址:https://dreamer.blue/blog/post/2017/02/20/UVALive-6582.dream

还不快抢沙发

添加新评论