CF1513D GCD and MST 题解
题面
对于一个序列,若有 \((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\),那么可以得到
既然题目要求的是最小生成树,那么我们贪心的去处理。考虑从小到大枚举边权,并计算当前边权在当前情况下可以最多联通多少个连通块(单点也看作连通块),显然对于 \(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;
}