题解：P11753 [COCI 2024/2025 #5] 塔楼 / Tornjevi

nekoboy · 2025-02-19 19:59:29 · 题解

无耻的提供更好的阅读体验。

思路（61 分）

暴力过不了，考虑优化。

最大公约数具有单调性：当区间扩展时，最大公约数不会增大。因此，对于每个位置 i，其作为区间最小值时可能成为最大公约数。

显而易见：若区间 [l, r] 的最大公约数是 g，则其子区间的最大公约数一定是 g 的倍数。反之，若某区间的最大公约数等于 h_i，则该区间必须包含 i，且所有元素的最大公约数为 h_i。

最后滑动窗口优化即可。

代码

只能得 61 分。

#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast", "-funroll-all-loops")
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

#define y1 kairiki
#define x first
#define y second

#define repeat(x, a, b) for(int x = a; x <= b; x ++)
#define rpless(x, a, b) for(int x = a; x >= b; x --)
#define repeatl(x, a, b) for(int x = a; x < b; x ++)
#define rplessr(x, a, b) for(int x = a; x > b; x --)

using namespace std;

const int N = 1e6 + 1;
int n, h[N], L[N], R[N], f[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    repeatl(i, 0, n) { cin >> h[i]; }

    stack<pii> st;
    repeatl(i, 0, n) {
        int s = i;

        while (!st.empty() && gcd(st.top().first, h[i]) == h[i]) {
            s = st.top().second;
            st.pop();
        }

        L[i] = s;
        st.push({h[i], s});
    }

    st = stack<pii> ();

    rpless(i, n - 1, 0) {
        int end = i;

        while (!st.empty() && gcd(st.top().first, h[i]) == h[i]) {
            end = st.top().second;
            st.pop();
        }

        R[i] = end;
        st.push({h[i], end});
    }

    repeatl(i, 0, n) {
        int t = h[i];

        for (int j = L[i]; j <= R[i]; ++j) {
            t = gcd(t, h[j]);

            if (t != h[i]) { break; }
        }

        if (t == h[i]) { f[i] = R[i] - L[i] + 1; }
        else {
            int l = i, r = i;

            while (l >= 0 && gcd(h[l], h[i]) == h[i]) { l--; }

            while (r < n && gcd(h[r], h[i]) == h[i]) { r++; }

            f[i] = r - l - 1;
        }
    }

    repeatl(i, 0, n) 
    { cout << f[i] << " "; }

    return 0;
}

优化

使用稀疏表预处理区间最大公约数，实现在 O(1) 时间内查询任意区间的最大公约数.

在计算 f_i 时，利用二分查找，减少不必要的计算。

代码

#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast", "-funroll-all-loops")
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>

#define y1 kairiki
#define x first
#define y second

#define repeat(x, a, b) for(int x = a; x <= b; x ++)
#define rpless(x, a, b) for(int x = a; x >= b; x --)
#define repeatl(x, a, b) for(int x = a; x < b; x ++)
#define rplessr(x, a, b) for(int x = a; x > b; x --)

using namespace std;

const int N = 1e6 + 1;
const int LOG = 20;
int n, h[N], L[N], R[N], f[N];
int st[N][LOG], log2_[N];

int query_gcd(int l, int r)
{
    int k = log2_[r - l + 1];
    return gcd(st[l][k], st[r - (1 << k) + 1][k]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    repeatl(i, 0, n) { cin >> h[i]; }

    log2_[1] = 0;
    repeat(i, 2, n) log2_[i] = log2_[i / 2] + 1;

    repeatl(i, 0, n) { st[i][0] = h[i]; }
    repeat(j, 1, LOG - 1) {
        for (int i = 0; i + (1 << j) <= n; i++) 
        { st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); }
    }

    stack<pii> st;
    repeatl(i, 0, n) {
        int s = i;

        while (!st.empty() && gcd(st.top().first, h[i]) == h[i]) {
            s = st.top().second;
            st.pop();
        }

        L[i] = s;
        st.push({h[i], s});
    }

    st = stack<pii>();
    rpless(i, n - 1, 0) {
        int end = i;

        while (!st.empty() && gcd(st.top().first, h[i]) == h[i]) {
            end = st.top().second;
            st.pop();
        }

        R[i] = end;
        st.push({h[i], end});
    }

    repeatl(i, 0, n) {
        int t = h[i];
        int l = L[i], r = R[i];

        if (query_gcd(l, r) == h[i]) { f[i] = r - l + 1; } 
        else {
            int tl = i, tr = i;

            while (tl >= 0 && query_gcd(tl, i) == h[i]) { tl--; }

            while (tr < n && query_gcd(i, tr) == h[i]) { tr++; }

            f[i] = tr - tl - 1;
        }
    }

    repeatl(i, 0, n) { cout << f[i] << " "; }

    return 0;
}