Hướng dẫn giải của Bedao Mini Contest 18 - FINDSET
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ả:
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