最新要闻

广告

手机

方程豹汽车首款车型豹5官图首发 硬派颜值气质拉满

方程豹汽车首款车型豹5官图首发 硬派颜值气质拉满

 消息称杭州新东方已退还暑期班剩余学费

消息称杭州新东方已退还暑期班剩余学费

家电

  1. 首页
  2. 移动通信
  3. 内容

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\)，那么可以得到

\[\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;}

关键词：