Hướng dẫn giải của Bedao Mini Contest 18 - FINDSET


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Giải bài toán với trường hợp ~m = 0~. Ta thấy với ~1 \le i \le n~, nếu tồn tại cặp ~(i, v)~ thì sẽ không thể tồn tại cặp ~(u, i)~, do đó, chúng ta có thể chia ~n~ số vào 2 nhóm sao cho các số nhóm ~1~ chỉ xuất hiện ở vị trí đầu trong các cặp và các số nhòm ~2~ chỉ xuất hiện ở vị trí sau trong các cặp.

Gọi số phần tử nhóm ~1~ và ~2~ lần lượt là ~x~ và ~y~.

Mỗi phần tử nhóm ~1~ kết hợp với từng phần tử nhóm ~2~ sẽ tạo ra được một cặp hợp lệ. Do đó có thể tạo được ~x.y~ cặp. Để số cặp được tạo ra nhiều nhất thì ~x = y = \frac{n}{2}~ với ~n~ chẵn và ~x = y + 1 = \lceil \frac{n}{2} \rceil~ với ~n~ lẻ. (Dễ dàng chứng minh được bằng bất đẳng thức toán học)

Gọi các nhóm ~A, B, C, D~ là các tập hợp không có phần tử lặp lại.

Duyệt qua ~m~ cặp ~(u, v)~ của đề bài: Thêm ~u~ vào nhóm ~C~, ~v~ vào nhóm ~D~

  • Nếu ~C~ có nhiều hơn hoặc bằng ~\lceil \frac{n}{2} \rceil~ phần tử: Ta thêm các số nhóm ~D~ vào ~A~ và thêm các số còn lại (không thuộc ~D~) tùy ý vào 2 nhóm ~A~ và ~B~ sao cho kích thước của 2 nhóm ~A~ và ~B~ tương tự như kích thước của 2 nhóm ~1~ và ~2~ nhắc tới ở trên.
  • Nếu ~C~ có ít hơn ~\lceil \frac{n}{2} \rceil~ phần tử: Ta thêm các số nhóm ~C~ vào ~B~ và thêm các số còn lại (không thuộc ~C~) tùy ý vào 2 nhóm ~A~ và ~B~ sao cho 2 nhóm ~A~ và ~B~ sao cho kích thước của 2 nhóm ~A~ và ~B~ tương tự như kích thước của 2 nhóm ~1~ và ~2~ nhắc tới ở trên.

Ta thấy nếu dựng các cặp của tập ~S~ dựa trên ~2~ nhóm ~A~ và ~B~ thì sẽ không có phần tử nào giống ~m~ cặp ban đầu và kích thước của ~S~ sẽ đạt cực đại.

Code mẫu

#include <bits/stdc++.h>

#define int long long
#define ll long long
#define II pair<int, int>
#define fs first
#define sc second
#define endl '\n'

const double PI = 3.141592653589793238;
const long long LINF = 1ll << 60;
const int INF = 1 << 30;
const int N = 2e3 + 5;

using namespace std;

bool cnt[N], cntC[N], cntD[N];
int A[N], B[N], C[N], D[N];
int s1, s2, s3, s4;

int32_t main() {
    srand(time(NULL));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // freopen("E.INP", "r", stdin);
    // freopen("E.OUT", "w", stdout);

    int n, m;
    cin >> m >> n;

    int u, v;
    for(int i = 1; i <= m; i++) {
        cin >> u >> v;
        if(!cntC[u]) {
            C[++s3] = u;
            cntC[u] = 1;
        }
        if(!cntD[v]) {
            D[++s4] = v;
            cntD[v] = 1;
        }
    }


    if(s3 < (n + 1) / 2) {
        for(int i = 1; i <= s3; i++) {
            B[++s2] = C[i];
            cnt[C[i]] = 1;
        }

        for(int i = 1; i <= n; i++) {
            if(!cnt[i]) {
                if(s2 < (n + 1) / 2) B[++s2] = i;
                else A[++s1] = i;
            }
        }
    } else {
        for(int i = 1; i <= s4; i++) {
            A[++s1] = D[i];
            cnt[D[i]] = 1;
        }

        for(int i = 1; i <= n; i++) {
            if(!cnt[i]) {
                if(s1 < (n + 1) / 2) A[++s1] = i;
                else B[++s2] = i;
            }
        }
    }

    //assert(s1 == (n + 1)  / 2 && s2 == n - (n + 1) / 2);
    cerr << n << ": " << s1 << " " << s2;

    cout << s1 * s2 << endl;
    vector<int> id1, id2;
    for(int i = 1; i <= s1; ++i) id1.emplace_back(i);
    for(int i = 1; i <= s2; ++i) id2.emplace_back(i);

    random_shuffle(id1.begin(), id1.end());
    random_shuffle(id2.begin(), id2.end());

    vector<pair<int, int>> ans;

    for(int i : id1){
        for(int j : id2) {
            ans.emplace_back(A[i], B[j]);
        }
    }

    random_shuffle(ans.begin(), ans.end());

    for(auto i : ans)
        cout << i.first << " " << i.second << "\n";

    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.