Hướng dẫn giải của Bedao Regular Contest 05 - DOMROOKS


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

Dựng một đồ thị ~2~ phía, ~2 \times 10^5~ đỉnh bên trái sẽ tương ứng cho các hàng, tương tự, ~2 \times 10^5~ đỉnh bên phải sẽ tương ứng cho các cột. ~2~ đỉnh bất kì ở ~2~ phía sẽ có cạnh nối khi và chỉ khi có một quân xe ở vị trí tương ứng.

Nhận xét: nếu đồ thị tạo ra được chu trình, thì tập hợp các quân xe trong chu trình đó sẽ phải cùng ở lại hoặc cùng bị gỡ bỏ. Còn nếu không phải là chu trình, các quân xe đó sẽ bị loại bỏ vì đỉnh nối các quân xe đó sẽ có bậc là ~1~ đồng nghĩa với việc hàng/cột đó sẽ bị thống trị.

Vì bậc của mỗi đỉnh trong đồ thị không quá ~2~ nên ta sử dụng ~DFS~ để đếm số chu trình trong ~O(N)~

Đáp án bài toán sẽ là: ~2^k~ với ~k~ là số chu trình.

Độ phức tạp: ~O(N)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef unsigned long long ull; 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = 5e5+5;
const int LOG = 20;
const ll MOD = 1e9+7;
const ll INF = 1e15+5;
const int SQRT = 44721;

ll add(ll a, ll b) { return (a+b) % MOD; }
ll sub(ll a, ll b) { return (a-b+MOD) % MOD; }
ll mul(ll a, ll b) { return (a*b) % MOD; }

int n;
bool visited[MAX];
vector<int> adj[MAX];

int pw(int val, int temp) {
    int curr = 1;

    while(temp > 0) {
        if(temp & 1) curr = mul(curr, val);
        val = mul(val, val);
        temp >>= 1;
    }

    return curr;
}

void dfs(int v) {
    visited[v] = 1;
    foa(u, adj[v]) {
        if(!visited[u]) dfs(u);
    }
}

int solve() {
    fo(i, 1, MAX-1) {
        if(!visited[i] && sz(adj[i]) == 1) dfs(i); 
    }
    int cyc = 0;
    fo(i, 1, MAX-1) {
        if(!visited[i] && sz(adj[i]) == 2) {
            cyc++;
            dfs(i);   
        } 
    }
    return pw(2, cyc);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
    cin >> n;
    fo(i, 1, n) {
        int r, c;
        cin >> r >> c;
        c += 2e5;
        adj[r].pb(c);
        adj[c].pb(r);
    }
    cout << solve();
}

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.