Codeforces Round 998 (Div. 3)题解

A题

统计$a_1+a_2$，$a_4-a_2$，$a_5-a_4$，三个数最多有多少个相同即可。

void solve() {
    int a1, a2, a4, a5;
    cin >> a1 >> a2 >> a4 >> a5;
    int x1 = a1 + a2, x2 = a4 - a2, x3 = a5 - a4;
    if (x1 == x2 || x2 == x3 || x1 == x3) {
        if (x1 == x2 && x2 == x3) {
            cout << 3 << "\n";
        } else {
            cout << 2 << "\n";
        }
    } else {
        cout << 1 << "\n";
    }
    
}

B题

方法一：将所有奶牛手中持有的牌全部排序，之后按第一张牌的大小确定排列，然后依次检查第二轮，第三轮…判断是否满足升序。

void solve() {
    int n, m;
    cin >> n >> m;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    
    for (auto &vec : a) {
        std::sort(vec.begin(), vec.end());
    }
    
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    
    std::sort(p.begin(), p.end(), [&](int i, int j) {
        return a[i].front() < a[j].front();
    });
    
    for (int i = 0; i < m; i++) {
        bool b = true;
        if (i > 0 && a[p[0]][i] < a[p[n - 1]][i - 1]) {
            cout << -1 << "\n";
            return;
        } 
        for (int j = 1; j < n; j++) {
            if (a[p[j]][i] < a[p[j - 1]][i]) {
                b = false;
                break;
            }
        }
        if (!b) {
            cout << -1 << "\n";
            return;
        }
    }
    for (int i : p) {
        cout << i + 1 << " ";
    }
    cout << "\n";
}

方法二：如果存在可行的排列，则每次奶牛的出牌顺序固定，每只牛手中的牌应该构成关于$n$的同余系。由此来判断是否存在可行的排列，存在再确定该排列。

void solve() {
    int n, m;
    cin >> n >> m;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
    
    for (int i = 0; i < n; i++) {
        a[i][0] %= n;
        for (int j = 1; j < m; j++) {
            if (a[i][j] % n != a[i][0]) {
                cout << -1 << "\n";
                return;
            }
        }
    }
    
    std::vector<int> p(n);
    std::iota(p.begin(), p.end(), 0);
    
    std::sort(p.begin(), p.end(), [&](int i, int j) -> bool {
        return a[i][0] < a[j][0];
    });
    for (int i : p) {
        cout << i + 1 << " ";
    }
    cout << "\n";
}

C题

找出最多有多少对数字$a$，$b$，满足$a+b=k$即可。

方法一：双指针

void solve() {
    int n, k;
    cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    std::sort(a.begin(), a.end());
    int p1 = 0, p2 = n - 1;
    int ans = 0;
    while (p1 < p2) {
        if (a[p1] + a[p2] == k) {
            ans++;
            p1++;
            p2--;
        } else if (a[p1] + a[p2] < k) {
            p1++;
        } else {
            p2--;
        }
    }
    cout << ans << "\n";
}

方法二：计数

void solve() {
    int n, k;
    cin >> n >> k;
    std::vector<int> cnt(n + 1);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cnt[a]++;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i * 2 < k && k - i <= n) {
            ans += std::min(cnt[i], cnt[k - i]);
        } else if (2 * i == k) {
            ans += cnt[i] / 2;
        }
    }
    cout << ans << "\n";
}

D题

贪心，看当前位置数字最多可以减去多少，如果减去一个可行的最大值后，仍然比下一个数字大，则不能转换为一个有序序列。

void solve() {
    int n;
    cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if (a[0] > a[1]) {
        cout << "NO\n";
        return;
    }
    std::vector<int> b(n);
    for (int i = 1; i < n; i++) {
        a[i] -= a[i - 1];
        if (a[i] < 0) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

E题

求要使得图F和图G的连通性相同，需要添加或者减去图F中最少多少条边。

使用并查集，对于图G中的一个连通块，这个连通块内的点组成一个点集${V_1}$ ，F图中取边集${(u,v)\in E_1 \and u, v\in V_1}$，看F图中$V_1$内的点组成的连通块个数为$n_1$，那么$n_1-1$就是F图在$V_1$中需要添加的边的数量，才能使这个子图连通，如果$(u,v)\in E_1 \and u,v在G图中不连通$那么这条边就属于应该删去的边。

方法一：

void solve() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;

    Union_Set usetg1(n + 1), usetg2(n + 1);
    std::vector<std::vector<int>> g1(n + 1, std::vector<int>());

    for (int i = 0; i < m1; i++) {
        int u, v;
        cin >> u >> v;
        g1[u].push_back(v);
        g1[v].push_back(u);
    }

    for (int i = 0; i < m2; i++) {
        int u, v;
        cin >> u >> v;
        usetg2.union_set(u, v);
    }

    std::map<int, int> mm;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (mm.find(usetg2.find_father(i)) == mm.end()) {
            mm[usetg2.find_father(i)] = cnt++;
        }
    }
    
    std::vector<std::vector<int>> g3(cnt, std::vector<int>());
    for (int i = 1; i <= n; i++) {
        g3[mm[usetg2.find_father(i)]].push_back(i);
    }

    int ans = 0;
    std::vector<bool> vis(n + 1);
    std::queue<int> q;
    
    for (auto &vec : g3) {
        
        std::set<int> ms;
        for (int i : vec) {
            if (vis[i]) continue;
            q.push(i);
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : g1[u]) {
                    if (!vis[v] && usetg2.in_same_set(u, v)) {
                        usetg1.union_set(u, v);
                        vis[v] = true;
                        q.push(v);
                    }
                }
            }
        }
        for (int i : vec) {
            ms.insert(usetg1.find_father(i));
        }
        
        ans += ms.size() - 1;
    }
    for (int u = 1; u <= n; u++) {
        for (int v : g1[u]) {
            usetg1.union_set(u, v);
        }
    }
    int ans2 = 0;
    for (int u = 1; u <= n; u++) {
        for (int v : g1[u]) {
            if (!usetg2.in_same_set(u, v)) {
                ans2++;
            }
        }
    }
    cout << ans + ans2 / 2 << "\n";
}

方法二：

void solve() {
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    DSU f(n), g(n);
    
    std::vector<PII> ef(m1);
    for (int i = 0; i < m1; i++) {
        cin >> ef[i].fi >> ef[i].se;
        ef[i].fi--;
        ef[i].se--;
    }
    
    int cntg = n;
    for (int i = 0; i < m2; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        cntg -= g.merge(u, v);
    }
    int ans = 0, cntf = n;
    for (auto [u, v] : ef) {
        if (g.same(u, v)) {
            cntf -= f.merge(u, v);
        } else {
            ans++;
        }
    }
    cout << ans + cntf - cntg << "\n";
}