# A

读题模拟即可

void solve() {
    int a1, a2, a4, a5;
    cin >> a1 >> a2 >> a4 >> a5;

    int x = a1 + a2, y = a4 - a2, z = a5 - a4;

    if (x == y && y == z)
        cout << 3 << endl;
    else if (x == y || y == z || x == z)
        cout << 2 << endl;
    else
        cout << 1 << endl;
}

# B

排序之后，出的每张牌都是有顺序的，只要扫描牌，都是 $+1$ 单增，即代表可以打完

struct Cow {
    int n;
    vector<int> card;
};

bool cmp(Cow a, Cow b) {
    return a.card[0] < b.card[0];
}

void solve() {
    Cow cow[N];

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cow[i].n = i;

        for (int j = 1, x; j <= m; j++) {
            cin >> x;
            cow[i].card.push_back(x);
        }

        sort(cow[i].card.begin(), cow[i].card.end());
    }

    sort(cow + 1, cow + n + 1, cmp);

    int cnt = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (cow[j].card[i - 1] == cnt)
                cnt++;
            else {
                cout << -1 << endl;
                return;
            }
        }
    }

    for (int i = 1; i <= n; i++)
        cout << cow[i].n << " ";

    cout << endl;
}

# C

成对的牌会抵消掉，数组要开大点

void solve(){
    memset(cnt, 0, sizeof cnt);

    cin >> n >> k;

    int maxx = 0;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x, maxx = max(maxx, x), cnt[x]++;
    }

    int res = 0;

    for (int i = 1; i <= k; i++) {
        int x = cnt[i], y = cnt[k - i], t = 0;

        if (i == k - i)
            t = x / 2, cnt[i] -= t;
        else
            t = min(x, y), cnt[i] -= t, cnt[k - i] -= t;
        
        res += t;
    }

    cout << res << endl;
}

# D

从第二个开始扫，全部都减掉，只要能扫完即代表数组可以操作成非递减

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    int idx = 2;

    while (idx <= n) {
        int t = min(a[idx - 1], a[idx]);

        a[idx - 1] -= t, a[idx] -= t;

        if (a[idx] < a[idx - 1]) {
            cout << "NO" << endl;
            return;
        }

        idx++;
    }

    cout << "YES" << endl;
}

# E

# 题目描述

You are given two simple undirected graphs $F$ and $G$ with $n$ vertices. $F$ has $m_1$ edges while $G$ has $m_2$ edges. You may perform one of the following two types of operations any number of times:

Select two integers $u$ and $v$ ( $1 \leq u,v \leq n$ ) such that there is an edge between $u$ and $v$ in $F$ . Then, remove that edge from $F$ .
Select two integers $u$ and $v$ ( $1 \leq u,v \leq n$ ) such that there is no edge between $u$ and $v$ in $F$ . Then, add an edge between $u$ and $v$ in $F$ .

Determine the minimum number of operations required such that for all integers $u$ and $v$ ( $1 \leq u,v \leq n$ ), there is a path from $u$ to $v$ in $F$ if and only if there is a path from $u$ to $v$ in $G$ .

# 题目解析

这题大意是，给两个无向图： $F,~given$ 。你可以进行两种操作

删除 $F$ 的一条边
往 $F$ 中添加一条边

问：要使得 $G$ 中的任意连通的两个点，在 $F$ 中也连通，最小需要多少次操作？

# 解析

这题用到了并查集维护
两个点连通 $\Leftrightarrow$ 在一个并查集内

int n, m1, m2, x, y, fa[N], fb[N];

int find(int x, int f[]) {
    return x == f[x] ? x : f[x] = find(f[x], f);
}

int unite(int x, int y, int f[]) {
    int fx = find(x, f), fy = find(y, f);

    if (fx != fy) {
        f[fx] = fy;
        return 1;
    }

    return 0;
}

int isConnected(int x, int y, int f[]) {
    return find(x, f) == find(y, f);
}

void solve(){
    vector<PII> v;
    
    cin >> n >> m1 >> m2;
    
    for (int i = 1; i <= n; i++)
        fa[i] = fb[i] = i;

    int res = 0, cnt1 = n, cnt2 = n;

    for (int i = 1; i <= m1; i++)
        cin >> x >> y, v.push_back({x, y});

    for (int i = 1; i <= m2; i++)
        cin >> x >> y, cnt2 -= unite(x, y, fb);

    for (auto side : v) {
        x = side.first, y = side.second;

        if (isConnected(x, y, fb) == 0)
            res++;
        else
            cnt1 -= unite(x, y, fa);
    }

    cout << res + cnt1 - cnt2 << endl;
}

模拟 Div3 并查集排序

# A

# B

# C

# D

# E

# 题目描述

# 题目解析

# 解析

数据结构期末复习

ABC-382