Codeforces 1513D - GCD and MST(設計解題)

題目大意

我們要生成出一個最小生成樹，設節點為 \(a_i\)，只要 \(a_i , a_i+1\) 就是 p 成本，但有一種情況下兩個點連接不是 p，，\(GCD(a_i, a_{i+1} , … , a_{j}) = min(a_i, a_{i+1} , … , a_{j}) \)，此時 \(a_i , a_j\) 也構成一條 edge。

請輸出最小的成本。

註：下面有時會將 \(GCD(a_i, a_{i+1} , … , a_{j}) = min(a_i, a_{i+1} , … , a_{j}) \) 省略講為 \(GCD = min\)

題目連結

重點觀念

• 了解 Kruskal 演算法
• 依照 Kruskal 進行優化
• 了解如何擴展左右數列的程式碼

分析

我們知道 Kruskal 是怎麼運作的，現在我們來看看這題，這題的 edge 比較簡單，只有 \(a_i , a_i+1\) 與 \(GCD = min\)的情況，剩下的就是降低成本。

首先我們可以找到題目裡的一個重大線索，\(GCD(a_i, a_{i+1} , … , a_{j}) = min(a_i, a_{i+1} , … , a_{j}) \)，這表示 \(a_i, a_{i+1} , … , a_{j}\) 每個結點都有跟 \(a_i\) 連接，因此權重都是相同，如果要生成最小生成樹，我們可以讓每個點都連接且 cose 都是 \(min(a_i)\)。

而其他不符合 \(GCD = min\) 的全部 cost 都是 p，並且他們都只有一條 edge \(a_i , a_i+1\) 連接。

因此我們只要對每個 \(a_i\) 進行排序，從最小的 \(a_i\) 開始向數列左右邊進行擴增直到 \(a_i\) 大於 p 為止，如果可以符合 \(GCD(a_i, a_{i+1} , … , a_{j}) = min(a_i, a_{i+1} , … , a_{j}) \)，就繼續擴增。

我們可以用此方式來優化我們對邊的計算，由於我們有 n 個節點，因此 edge 會是 n-1，在前面我們推出無論是 \(gcd = min\) or 成本 p，我們都可以讓每個點都連接；因此我們只要記錄有幾個邊是 \(gcd = min\)，剩下的 edge cost 就是 p。

參考連結

Codeforces Round #714 (Div. 2) D. GCD and MST by 渴望成为大佬菜鸡，獲益良多，很感謝QQQ
Codeforces1513 D. GCD and MST（思维，MST） by live4m
CodeForces 1504E : GCD and MST 思维 by 匿枫

心得

太棒了，這題目…QQQQ。把我考得落花流水，我一開始都是往實踐 Kruskal 的方式去實作，一直想不通要怎麼去解決 \(gcd = min\) 的問題。

現在看到後才被打通自己的思路，其實不需要去想邊要怎麼連接，因為每一種連接方式(p , \(gcd = min\))的 edge cost 都相同，我們只需要去紀錄每種連接方式裡有幾個邊、cost 多少就好。

總之，寫 codeforces 的題目常常能夠讓自己的思考邏輯更加發散，透過發散來讓自己的思考能力變得更好，更加寬廣，然後進行收斂，得到最好答案。
希望在任何地方我都能運用此技巧。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define LOCAL
using namespace std;
const int MAXN = 300000;
int t, n, p, temp;
deque<pair<int,int>> nodes; //first 為 a[i] 值，second 為 index，是為了方便後面排序而這樣設計
int a[MAXN], visit[MAXN]; //visit 判斷此節點有沒有與其他邊連接

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        memset(visit, 0, sizeof(visit)); //清除，以避免資料被干擾
        nodes.clear();

        cin >> n >> p; 
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            nodes.push_back({a[i], i});
        }
        sort(nodes.begin(), nodes.end());

        int ans = 0, remain_edge = n-1; //ans 答案，remain_edge 剩餘的邊數量
        while(nodes.size()){ //開始進行擴展
            pair<int,int> node = nodes.front();
            //cout << node.first << ' ' << node.second << '\n';
            nodes.pop_front();
            if(node.first > p) break; //如果 a[i] 值大於 p，則沒必要改變邊的 cost
            if(visit[node.second]) continue; //此節點已經與其他邊連結

            int l = node.second, r = node.second;
            while(l > 1 && !visit[l] && a[l-1] % node.first == 0) l--; //向左擴展
            while(r < n && !visit[r] && a[r+1] % node.first == 0) r++; //向右擴展
            //while(不超過左邊邊界 && r 並沒有被其他 gcd = min 使用 &&
            // gcd(a[i] , a[r-1]) == 0 )，向左擴展邏輯也是如此
            //需要特別注意的是，!visit[r] 是驗證此節點是否有沒有與其他 min = gcd 連通，有的話就不行
            // a[r+1] % node.first == 0 則是判斷是否可以延伸，如果 a[r+1] 小於 node.first 則不可能符合此邏輯式，也表示下個點不可能可以連通，直接將 r 停留在此就好。
            // l 邏輯也是相同

            //we sum edge, not node.
            //so we consider visit[i] used or not,
            //if visit[i] is true, then node[i] small than node.first
            //then don't be extend (left or right) sequence.

            for(int i = l; i <= r; i++) visit[i] = 1; //將此區間表示已用過
            ans += node.first * (r-l); //紀錄區間內的所有邊成本
            remain_edge -= (r-l); //剩下的邊減去區間的所有邊數量
            //cout << "l r " << l << ' ' << r << '\n';
            //cout << "ans " << ans << '\n';
        }
        //cout << "remain_edge " << remain_edge << '\n';
        ans += remain_edge * p; //ans +  p * 剩餘邊長數量
        cout << ans << '\n'; //輸出答案
    }
    return 0;
}