Falling Anvils

一道涉及积分的题，可以画图来解决。想要找到 $p\geq 4q$的部分，找到那个部分的面积与总面积的比。

注意一点，如果a,b都为0的话，需要特判一下，否则会输出“nan”

Mahmoud and a Dictionary

扩展域并查集的模板题，或许还可以复习一下带权并查集

#include <bits/stdc++.h>

using namespace std;

struct DSU {
    vector<int> f;
    DSU(int n) : f(n * 2) {iota(f.begin(), f.end(), 0); }
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return f[x];
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    bool merge(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        f[x] = y;
        return true;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;
    vector<string> s(n);
    for (auto &i : s) cin >> i;
    map<string, int> mp;
    for (int i = 0; i < n; i ++) {
        mp[s[i]] = i;
    }

    DSU dsu(n);

    int op;
    string S, T;
    int a, b;
    for (int i = 0; i < m; i ++) {
        cin >> op >> S >> T;
        a = mp[S], b = mp[T];
        if (op == 1) {
            if (dsu.same(a + n, b)) {
                cout << "NO\n";
                continue;
            }
            dsu.merge(a, b); // 分享了他们的敌人和朋友
            dsu.merge(a + n, b + n);
        } else {
            if (dsu.same(a, b)) {
                cout << "NO\n";
                continue;
            }
            dsu.merge(a, b + n);
            dsu.merge(a + n, b);
        }
        cout << "YES\n";
    }

    for (int i = 0; i < q; i ++) {
        cin >> S >> T;
        a = mp[S], b = mp[T];
        if (dsu.same(a, b)) cout << 1 << '\n';
        else if (dsu.same(a, b + n)) cout << 2 << '\n';
        else cout << 3 << '\n';
    }

    return 0;
}