Bài toán Badge (A)

Với ràng buộc n \leq 1000, ta có thể áp dụng tìm kiếm chiều sâu (DFS) kết hợp mảng đánh dấu. Ý tưởng chính: với mỗi đỉnh xuất phát, duyệt theo liên kết cho đến khi gặp đỉnh đã thăm trước đó.

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1005;

int n, ket_qua, lien_ket[MAX];
bool da_tham[MAX];

void DFS(int u) {
    if (ket_qua != -1) return;
    if (da_tham[u]) {
        ket_qua = u;
        return;
    }
    da_tham[u] = true;
    DFS(lien_ket[u]);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> lien_ket[i];
    
    for (int diem_xuat_phat = 1; diem_xuat_phat <= n; diem_xuat_phat++) {
        fill(da_tham, da_tham + n + 1, false);
        ket_qua = -1;
        DFS(diem_xuat_phat);
        cout << ket_qua << " ";
    }
    return 0;
}

Bài toán Line++ (B)

Với n \leq 2000, thực hiện BFS từ mọi đỉnh xuất phát. Lưu ý: kết quả cần chia đôi do mỗi đường đi được tính hai lần (thuận và ngược).

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAX = 2005;

int n, X, Y, khoang_cach[MAX], ket_qua[MAX];
vector<int> do_thi[MAX];

void BFS(int uoc) {
    queue<int> hang_doi;
    memset(khoang_cach, -1, sizeof(khoang_cach));
    khoang_cach[uoc] = 0;
    hang_doi.push(uoc);
    
    while (!hang_doi.empty()) {
        int u = hang_doi.front(); hang_doi.pop();
        for (int v : do_thi[u]) {
            if (khoang_cach[v] == -1) {
                khoang_cach[v] = khoang_cach[u] + 1;
                hang_doi.push(v);
            }
        }
    }
}

int main() {
    cin >> n >> X >> Y;
    do_thi[X].push_back(Y);
    do_thi[Y].push_back(X);
    
    for (int i = 1; i < n; i++) {
        do_thi[i].push_back(i+1);
        do_thi[i+1].push_back(i);
    }
    
    for (int diem = 1; diem <= n; diem++) {
        BFS(diem);
        for (int i = 1; i <= n; i++) 
            if (khoang_cach[i] > 0) 
                ket_qua[khoang_cach[i]]++;
    }
    
    for (int i = 1; i < n; i++) 
        cout << ket_qua[i]/2 << "\n";
    return 0;
}

Bài toán 755 (C)

Sử dụng BFS để sinh số chỉ chứa chữ số 3, 5, 7. Kiểm tra điều kiện: cả ba chữ số phải xuất hiện ít nhất một lần. Giới hạn n \leq 10^9 nhưng số lượng số sinh ra chỉ khoảng 3^9.

#include <iostream>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;

struct So {
    ll gia_tri;
    bool co_3, co_5, co_7;
};

ll n, dem;
map<ll, bool> da_sinh;

int main() {
    cin >> n;
    queue<So> hang_doi;
    hang_doi.push({0, false, false, false});
    da_sinh[0] = true;
    
    while (!hang_doi.empty()) {
        So hien_tai = hang_doi.front(); hang_doi.pop();
        if (hien_tai.co_3 && hien_tai.co_5 && hien_tai.co_7) 
            dem++;
        
        for (ll so : {3, 5, 7}) {
            ll moi = hien_tai.gia_tri * 10 + so;
            if (moi > n || da_sinh[moi]) continue;
            
            da_sinh[moi] = true;
            hang_doi.push({
                moi,
                hien_tai.co_3 || (so == 3),
                hien_tai.co_5 || (so == 5),
                hien_tai.co_7 || (so == 7)
            });
        }
    }
    cout << dem;
    return 0;
}

Bài toán Hành Trình (D)

Với đồ thị dạng cây, thực hiện DFS từ gốc (đỉnh 1). Tính kỳ vọng độ sâu lá bằng cách nhân độ sâu với xác suất đến được đỉnh đó. Xác suất được cập nhật dựa trên số con của mỗi đỉnh.

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
typedef long double ld;
const int MAX = 1e5+5;

int n, do_sau[MAX];
ld xac_suat[MAX], tong;
vector<int> ke[MAX];

void DFS(int u, int cha) {
    do_sau[u] = do_sau[cha] + 1;
    int so_con = 0;
    for (int v : ke[u]) 
        if (v != cha) so_con++;
    
    for (int v : ke[u]) {
        if (v == cha) continue;
        xac_suat[v] = xac_suat[u] / so_con;
        DFS(v, u);
    }
    
    if (so_con == 0) 
        tong += xac_suat[u] * do_sau[u];
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    
    xac_suat[1] = 1.0;
    DFS(1, 0);
    cout << fixed << setprecision(10) << tong;
    return 0;
}

Bài toán Hai Nút Bấm (E)

Áp dụng BFS trên không gian trạng thái với hai thao tác: giảm 1 hoặc nhân đôi. Giới hạn giá trị trạng thái tối đa khoảng 2 \times 10^4.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX = 1e5;

int n, m, buoc_di[MAX+5];
bool da_den[MAX+5];

int main() {
    cin >> n >> m;
    memset(buoc_di, -1, sizeof(buoc_di));
    queue<int> q;
    q.push(n);
    buoc_di[n] = 0;
    da_den[n] = true;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u == m) break;
        
        if (u - 1 >= 0 && !da_den[u-1]) {
            da_den[u-1] = true;
            buoc_di[u-1] = buoc_di[u] + 1;
            q.push(u-1);
        }
        
        if (u * 2 <= MAX && !da_den[u*2]) {
            da_den[u*2] = true;
            buoc_di[u*2] = buoc_di[u] + 1;
            q.push(u*2);
        }
    }
    cout << buoc_di[m];
    return 0;
}