CF1513D GCD and MST 题解-526互联

题面

对于一个序列，若有 \((i,j)(i < j)\)，若 \(\gcd_{k=i}^j a_k =\min_{k=i}^j a_k\)，则连一条无向边 \((i,j)\)，边权为 \(\min_{k=i}^j a_k\)；若有 \((i,j)(i+1=j)\)，连一条无向边 \((i,j)\)，边权为 \(p\)。

给定一个长度为 \(n\) 的序列，求连边所构成图的 MST 的边权之和，多测。

题意

首先考虑转化限制条件，假设我们在 \(l, r\) 之间连了一条边（\(l < r\)），记 \(v = \min\limits_{i = l}^{r}a_i\)，那么可以得到

\[\gcd\limits_{i = l}^{r}a_i = \min\limits_{i = l}^{r}a_i \Leftrightarrow \forall i \in \left[l,r\right], v \mid a_i \]

既然题目要求的是最小生成树，那么我们贪心的去处理。考虑从小到大枚举边权，并计算当前边权在当前情况下可以最多联通多少个连通块（单点也看作连通块），显然对于 \(a_i\) 来说，可以以边权 \(a_i\) 联通的点对 \(\left(l, r\right)\) 一定满足 \(i \in \left[l,r\right] \land \forall k \in \left[l,r\right], a_i \mid a_k\)，从 \(i\) 开始两侧遍历即可最大化该区间，因为边权是从小到大枚举的，所以在当前情况下最大化区间一定不劣。同时注意一点，如果左右边界扩充到了已经被其他点联通过的点也需要停止扩充，如果 \(a_i \ge p\) 那么剩下的未联通的联通块直接使用第二种边联通即可。

Code

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<bool> bitset;

int main() {
    valueType T;

    std::cin >> T;

    for (int testcase = 0; testcase < T; ++testcase) {
        valueType N, P;

        std::cin >> N >> P;

        ValueVector source(N);
        PairVector map(N);

        for (valueType i = 0; i < N; ++i) {
            std::cin >> source[i];

            map[i] = std::make_pair(source[i], i);
        }

        std::sort(map.begin(), map.end());

        bitset visited(N, false);

        valueType ans = 0, count = 0;

        for (auto const &value: map) {
            if (value.first >= P)
                break;

            valueType const index = value.second;

            if (visited[index])
                continue;

            visited[index] = true;

            valueType leftBound = index, rightBound = index;

            while (leftBound > 0 && source[leftBound - 1] % source[index] == 0) {
                --leftBound;

                if (visited[leftBound])
                    break;

                visited[leftBound] = true;
            }

            while (rightBound < N - 1 && source[rightBound + 1] % source[index] == 0) {
                ++rightBound;

                if (visited[rightBound])
                    break;

                visited[rightBound] = true;
            }

            count += rightBound - leftBound;

            ans += source[index] * (rightBound - leftBound);
        }

        ans += (N - 1 - count) * P;

        std::cout << ans << '\n';
    }

    std::cout << std::flush;

    return 0;
}

collection movie 1513 uva