题解 | #小辰打比赛#

小辰打比赛

https://ac.nowcoder.com/acm/contest/69791/A

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏


F. 小辰刚学 gcd

我多么想,出题人,你可以亚撒西一点。

关于大量区间查询问题,还有gcd,最值,位运算这类,往往可以借助ST来加速。

这题比较特殊,可以分治二分(不知道这样说法对不对)来快速计算整个区间的不同gcd数。

可惜这个思路TLE了,感觉被严格卡复杂度了,多一个log也不行。

Java卡在56%, 等价C++(常数优化后)卡90%。


其实正解的思路,在数组 按与/或操作,区间查询最值等等问题,经常有出现。

就是维护变动的点列表

位运算的话,最多32位,所以最多32个点

而gcd的话,其实也是一样,因为最小的质因子为2, 而2^32是最大的整数

而arr[i + 1]变动点的列表,可以基于arr[j]的基础上,生成。

因此整个是时间复杂度为 O(32n)


贴一个chatgpt翻译后的c++代码

原一模一样的java代码被卡在70%, 数据还是卡常了。

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <cmath>  
  
using namespace std;  
  
long gcd(long a, long b) {  
    return b == 0 ? a : gcd(b, a % b);  
}  
  
int main() {  
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n, q;  
    cin >> n >> q;  
    vector<long> arr(n);  
    vector<vector<pair<long, int>>> g(n);  
    for (int i = 0; i < n; i++) {  
        cin >> arr[i];  
        long v = arr[i];  
        g[i].push_back({v, i});  
        if (i > 0) {  
            auto& prev = g[i - 1];  
            for (auto& pair : prev) {  
                long tv = gcd(v, pair.first);  
                if (tv != v) {  
                    g[i].push_back({tv, pair.second});  
                }  
                v = tv;  
                if (v == 1) break;  
            }  
        }  
    }  
    vector<int> res;  
    for (int i = 0; i < q; i++) {  
        int l, r;  
        cin >> l >> r;  
        l--;  // adjust for zero-based indexing  
        r--;  // adjust for zero-based indexing  
        auto& rightList = g[r];  
        int left = 0, right = rightList.size() - 1;  
        while (left <= right) {  
            int mid = left + (right - left) / 2;  
            if (rightList[mid].second >= l) {  
                left = mid + 1;  
            } else {  
                right = mid - 1;  
            }  
        }  
        res.push_back(left);  
    }  
    for (auto& val : res) cout << val << "\n";  
    return 0;  
}
全部评论

相关推荐

5 2 评论
分享
牛客网
牛客企业服务