Codeforces 1483D - Playlist(Disjoint Set 並查集)

題目大意

有一個數列可以被一種方式移除，只要當前的數值與下一個數值是 \(gcd = 1\) 的情況就將後面的數值取出並記錄 index。

請輸出有幾個數值被取出，並且那些 index 為何。

題目連結

重點觀念

• 了解 GCD
• 減少重複比對
• 熟悉並查集

分析

我們可以先稍微進行分析

• 只要 gcd == 1 就是移除後面的數值
• 重複的比對相同數值是題目絕對不允許的

這時我們可以用一種方式來進行思考，如果我們將 gcd == 1 後不將後者數值刪除，而是告訴前者數值的下一個數值是哪個的時候是不是可以解決問題？

舉例：

index: 1 2 3
value: 1 2 3
merge: 1 2 3

其中前兩項 gcd = 1，這時我們只修改 merge 為

index: 1 2 3
value: 1 2 3
merge: 2 2 3

表示我們現在只要到 index 1 的時候就直接到 index 3，跳過被合併的 2，這樣我們可以減少大量的刪
除動作。

現在我們可以知道一件事 merge 中相同數值的第一個 index 必定是尚未被消除過的數值，其他的 index 一定有被消除過且最後一個 index 必定等同於 merge 的數值。
這裡我們寫程式方便，會有一個 del 陣列來記錄被消除的 index。

再來我們要減少重複比對，這時候就需要一個 queue 了，由於我們知道 gcd(x,y) 與 gcd(y,x)，一定相同，因此我們可以降低重複比對。

假如現在有三個值 x,y,z，且都 \(gcd != 1\)，那我們只要做三遍 gcd 就可以知道這三個數值保證 \(gcd != 1\)

gcd(x,y)
gcd(y,z)
gcd(z,x)

這時我們就又知道了一件事情，每個數值都只會跟自己的下一個數值做 gcd，因此我們的 queue 只要記錄 gcd 的前項就好，後項不需要紀錄。

那有沒有可能後項會被 gcd 的操作給移除掉? 不可能。
用上面的舉例，如果 gcd(x,y)，y 沒有被移除，那 y 在下次的 gcd(y,z) 不可能會被移除。

因此我們可以得出結論

• 使用並查集來 merge 消除的數值
• 我們用 queue 紀錄 gcd 的第一項
• 如果 gcd(x,y) == 1，那就讓 vector 紀錄 y，並且 queue.push(x)，因為 x 的下一個數值不在是 y，我們沒辦法保證 gcd(x,z) == 1，需要重做才知道。

參考連結

Codeforces Round #709 (Div. 1, based on Technocup 2021 Final Round) by 一只蒟蒻
Codeforces Round #709 (Div. 1, based on Technocup 2021 Final Round) by Wallace
Codeforces Round #709 / Technocup 2021 Final Round — Unofficial Editorial by Geothermal’s blog

心得

這題學到很多，第一次意識到 disjoint set 也可以這樣操作，學了很多啊。

希望自己透過這樣子的學習可以讓自己變得更強，並且更加靈活地應用在生活上！

題目程式碼

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

#include<bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 1e6;
int a[MAXN], fa[MAXN], del[MAXN]; //a 是數值，fa 是 merge，del 是那些 index 被消除過
int t, n;
vector<int> record; //紀錄答案
deque<int> q;

int find_root(int x){ //並查集
    return fa[x] == x ? x : fa[x] = find_root(fa[x]);
}

int main(){
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        q.clear(); //清空，避免影響此次答案
        record.clear();
        for(int i = 1; i <= n; i++){ //輸入資料
            cin >> a[i];
            fa[i] = i;
            del[i] = 0; //清空
            q.push_back(i); //將未比對的 gcd 的數值放入 q
        }

        while(!q.empty()){ //如果空了表示，全部都有比對過
            int u = q.front(); q.pop_front(); //
            if(del[u]) continue; //如果這邊之前有被消除過，就不需要比對
            int v = (find_root(u)+1) % n; //下一個未被消除的位置
            if(v == 0) v = n; //如果是 0 是因為 mod 的問題，因此改回 n

            if(__gcd(a[u], a[v]) == 1){ //可以被消除
                record.push_back(v); //紀錄消除的 index
                int fu = find_root(u); //合併
                int fv = find_root(v);
                fa[fu] = fv; //讓 fv 的值給到 fu，f 表示 father
                del[v] = 1; //v 被移除
                q.push_back(u); //u 被放入，因為 gcd 的 v 被移除掉，他接下來還會匹配到新的 v
            }
        }
        cout << record.size(); //輸出答案
        for(auto it: record) cout << ' ' << it;
        cout << '\n';
    }
}