题解 | # 冰茶鸡 #

题目一：https://www.luogu.com.cn/problem/P1955

模板

注意离散化，下面给出两种离散化：

map<int, int> ma;
int idx = 0;
for(int i = 1; i <= n; i ++){
    int op, x, y; cin >> x >> y >> op;
    if(!ma[x]) ma[x] = ++ idx;
    if(!ma[y]) ma[y] = ++ idx;
    a[i] = {op, {ma[x], ma[y]}};
}

vector<int> v(2 * n + 10);
int idx = 0;
for(int i = 1; i <= n; i ++){
    int op, x, y; cin >> x >> y >> op;
    v[++ idx] = x;
    v[++ idx] = y;
    a[i] = {op, {x, y}};
}
sort(v.begin() + 1, v.begin() + 1 + idx);
int len = unique(v.begin() + 1, v.begin() + 1 + idx) - (v.begin() + 1);
int x = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].second.first) - v.begin();
int y = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].second.second) - v.begin();
int fx = find(x), fy = find(y);

两者差不多，如果不卡时间的话，使用 $map$ 更方便，但是实际上更耗时

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 200000 + 100;

int p[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void solve(){

    int n; cin >> n;
    vector<pair<int, pair<int, int> > > a(n + 10);
    vector<int> v(2 * n + 10);
    int idx = 0;
    for(int i = 1; i <= n; i ++){
        int op, x, y; cin >> x >> y >> op;
        v[++ idx] = x;
        v[++ idx] = y;
        a[i] = {op, {x, y}};
    }
    sort(v.begin() + 1, v.begin() + 1 + idx);
    int len = unique(v.begin() + 1, v.begin() + 1 + idx) - (v.begin() + 1);
    for(int i = 1; i <= len + 10; i ++) p[i] = i;
    for(int i = 1; i <= n; i ++){
        if(a[i].first == 1){
            int x = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].second.first) - v.begin();
            int y = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].second.second) - v.begin();
            int fx = find(x), fy = find(y);
            if(fx != fy) p[fx] = fy;
        }
    }
    for(int i = 1; i <= n; i ++){
        if(a[i].first == 0){
            int x = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].second.first) - v.begin();
            int y = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].second.second) - v.begin();
            int fx = find(x), fy = find(y);
            if(fx == fy){
                cout << "NO" << endl;
                return; 
            }
        }
    }
    cout << "YES" << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}

题目二：https://www.luogu.com.cn/problem/UVA1316

贪心的思想，优先考虑卖出利润大的商品，并对每一个商品，在它过期之前尽量晚卖出--占用较晚的时间，显然对其他商品具有“决策包容性”。具体的，将商品的利润从大到小排序，对于每一个商品，如果它在第 $d$ 天之后过期，就在并查集中查询 $d$ 的树根（记为 $r$ ）。如果 $r>0$ ，则把该商品安排在第 $r$ 天卖出，合并 $r$ 与 $r - 1$ （令 $r$ 为 $r - 1$ 的子节点），答案累加该商品的利润。

总代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long

const int N = 10000 + 100;


int p[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}

signed main(){
    
    int n;
    while(cin >> n){
        vector<pair<int, int> > a(n + 10);
        for(int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second;
        sort(a.begin() + 1, a.begin() + 1 + n, cmp);
        for(int i = 1; i <= 10000; i ++) p[i] = i;
        int ans = 0;
        for(int i = 1; i <= n; i ++){
            int fx = find(a[i].second);
            if(fx > 0){
                ans += a[i].first;
                p[fx] = fx - 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

题目三：https://www.luogu.com.cn/problem/P1196

权值并查集：并查集实际上是由若干棵树构成的森林，我们可以在树中的每一条边上记录一个权值，即维护一个数组 $d$ ，用 $d[x]$ 保存节点 $x$ 到父节点 $p[x]$ 之间的权值。在每次路径压缩后，每个访问的节点都会直接指向树根，如果我们同时更新这些节点的 $d$ 值，就可以利用路径压缩过程来统计每个节点到树根之间的路径上的一些信息。

这道题目，首先没有路径压缩前， $p[x]$ 表示的是排在 $x$ 号战舰前面的那个战舰的编号，用 $d[x]$ 表示 $x$ 到其树根的距离，那么如果 $x$ 和 $y$ 在同一个集合中，那么它们之间的距离直接就是 $abs(d[x]-d[y])-1$

$find$ 函数路径压缩过程中，首先得更新当前节点 $x$ 的 $d[x]$ ，因为有可能 $p[x]$ 在某次操作中成为其他节点的子节点了，最后再设置 $p[x]=root$

int find(int x){
    if(x != p[x]){
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

这就是刚才说的某次操作，那么此时 $fx$ 成为 $fy$ 的子节点，所以 $d[fx]$ 就等于 $fy$ 集合的大小，同时更新 $fy$ 集合的大小，最后设置 $p[fx] = fy$

if(op == 'M'){
    int fx = find(x), fy = find(y);
    d[fx] = cnt[fy];
    cnt[fy] += cnt[fx];
    p[fx] = fy;
}

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 30000 + 100;

int p[N], cnt[N], d[N];

int find(int x){
    if(x != p[x]){
        int root = find(p[x]);
        d[x] += d[p[x]];
        p[x] = root;
    }
    return p[x];
}

void solve(){
    
    int n; cin >> n;
    for(int i = 1; i <= 30000; i ++){
        p[i] = i;
        cnt[i] = 1;
        d[i] = 0;
    }    
    for(int i = 1; i <= n; i ++){
        char op;
        int x, y;
        cin >> op >> x >> y;
        if(op == 'M'){
            int fx = find(x), fy = find(y);
            d[fx] = cnt[fy];
            cnt[fy] += cnt[fx];
            p[fx] = fy;
        }
        else{
            int fx = find(x), fy = find(y);
            if(fx != fy) cout << "-1" << endl;
            else cout << abs(d[x] - d[y]) - 1 << endl;
        }
    }
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目四：https://www.luogu.com.cn/problem/P5937

用 $sum[i]$ 表示序列 $S$ 中 $[1,i]$ 中 $1$ 的个数，那么：

如果 $S[l,r]$ 中有偶数个 $1$ ，则 $sum[r]-sum[l-1]$ 是偶数，则 $sum[r]$ 与 $sum[l-1]$ 的奇偶性相同

如果 $S[l,r]$ 中有奇数个 $1$ ，则 $sum[r]-sum[l-1]$ 是奇数，则 $sum[r]$ 与 $sum[l-1]$ 的奇偶性不同

用权值并查集做：
设 $d[x]$ 表示的是 $x$ 与其根节点的关系，如果 $d[x]=0$ ，表示奇偶性相同，否则不相同

更新后，原来以 $p[fx]$ 的集合里面的 $d$ 需要更新，只需要更新 $d[fx]$ ，原集合中的值在 $find$ 中可被更新，所以：

如果 $x$ 与 $y$ 奇偶性相同，那么 $d[x]\oplus d[y] \oplus d[p[x]] = 0/1$ ，再由异或的交换律得到 $d[p[x]] = d[x] \oplus d[y] \oplus 0/1$

else{
    p[fx] = fy;
    if(a[i].second == "even") d[fx] = d[x] ^ d[y] ^ 0;
    else d[fx] = d[x] ^ d[y] ^ 1;
}

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 10000 + 100;
int n, m, p[N], d[N];

int find(int x){
    if(x != p[x]){
        int root = find(p[x]);
        d[x] ^= d[p[x]];
        p[x] = root;
    }
    return p[x];
}

void solve(){
    
    cin >> n >> m;
    vector<pair<pair<int, int>, string> > a(m + 10);
    vector<int> v(2 * m + 10);
    int idx = 0;
    for(int i = 1; i <= m; i ++){
        int x, y;
        string s;
        cin >> x >> y >> s;
        v[++ idx] = x - 1;
        v[++ idx] = y;
        a[i] = {{x - 1, y}, s};
    }    
    sort(v.begin() + 1, v.begin() + 1 + idx);
    int len = unique(v.begin() + 1, v.begin() + 1 + idx) - (v.begin() + 1);

    for(int i = 1; i <= len + 10; i ++){
        p[i] = i;
        d[i] = 0;
    }

    for(int i = 1; i <= m; i ++){
        int x = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].first.first) - v.begin();
        int y = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].first.second) - v.begin();
        int fx = find(x), fy = find(y);
        if(fx == fy){
            if(a[i].second == "even"){
                if(d[x] != d[y]){
                    cout << i - 1 << endl;
                    return ;
                }
            }
            else{
                if(d[x] == d[y]){
                    cout << i - 1 << endl;
                    return ;
                }
            }
        }
        else{
            p[fx] = fy;
            if(a[i].second == "even") d[fx] = d[x] ^ d[y] ^ 0;
            else d[fx] = d[x] ^ d[y] ^ 1;
        }
    }
    cout << m << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

也可以用扩展域并查集：

注意两倍的空间以及是加 $len$ ，不是加 $idx$ 或者 $n$

for(int i = 1; i <= 2 * len + 10; i ++) p[i] = i;
int fxx = find(x + len), fyy = find(y + len);

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 20000 + 100;

int n, m;

int p[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void solve(){
    
    cin >> n >> m;
    vector<int> v(2 * m + 10);
    int idx = 0;
    vector<pair<pair<int, int>, string> > a(m + 10);
    for(int i = 1; i <= m; i ++){
        int x, y;
        string s;
        cin >> x >> y >> s;
        v[++ idx] = x - 1;
        v[++ idx] = y;
        a[i] = {{x - 1, y}, s};
    }
    sort(v.begin() + 1, v.begin() + 1 + idx);
    int len = unique(v.begin() + 1, v.begin() + 1 + idx) - (v.begin() + 1);
    for(int i = 1; i <= 2 * len + 10; i ++) p[i] = i;
    for(int i = 1; i <= m; i ++){
        int x = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].first.first) - v.begin();
        int y = lower_bound(v.begin() + 1, v.begin() + 1 + len, a[i].first.second) - v.begin();
        int fx = find(x), fy = find(y);
        int fxx = find(x + len), fyy = find(y + len);
        if(a[i].second == "even"){
            if(fx == fyy){
                cout << i - 1 << endl;
                return ;
            }
            if(fx != fy){
                p[fx] = fy;
                p[fxx] = fyy;
            }
        }
        else{
            if(fx == fy){
                cout << i - 1 << endl;
                return ;
            }
            else{
                p[fx] = fyy;
                p[fxx] = fy;
            }
        }
    }
    cout << m << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目五：https://www.luogu.com.cn/problem/P2024

太经典的扩展域并查集题目了

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 3 * 50000 + 100;

int n, m, p[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void solve(){
    
    cin >> n >> m;
    for(int i = 1; i <= 3 * n; i ++) p[i] = i;
    int ans = 0;
    for(int i = 1; i <= m; i ++){
        int op, x, y; cin >> op >> x >> y;
        if(x > n || y > n){
            ans ++;
            continue;
        }
        if(op == 2 && x == y){
            ans ++;
            continue;
        }

        //同类，猎物，天敌
        int fx1 = find(x), fy1 = find(y);
        int fx2 = find(x + n), fy2 = find(y + n);
        int fx3 = find(x + n + n), fy3 = find(y + n + n);
        if(op == 1){
            if(fx1 == fy2 || fx1 == fy3){
                ans ++;
                continue;
            }
            if(fx1 != fy1){
                p[fx1] = fy1;
                p[fx2] = fy2;
                p[fx3] = fy3;
            }
        }   
        else{
            if(fx1 == fy1 || fx1 == fy2){
                ans ++;
                continue;
            }
            if(fx1 != fy3){
                p[fx1] = fy3;
                p[fx2] = fy1;
                p[fx3] = fy2;
            }
        }
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}