(资料图片)
题面
对于一个序列，若有 \((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 typedef long long valueType;typedef std::vector ValueVector;typedef std::pair ValuePair;typedef std::vector PairVector;typedef std::vector 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;}