Giải bài tập cuộc thi AtCoder Beginner Contest 451

Bài A - Kiểm tra độ dài chuỗi

Hãy kiểm tra xem độ dài của chuỗi có phải là bội số của \(5\) hay không.
Xem mã nguồn

#include 
using namespace std;

int main(){
    string chuoi;
    cin >> chuoi;
    int doDai = chuoi.length();
    
    cout << (doDai % 5 == 0 ? "Yes" : "No");
    return 0;
}

Bài B - Thay đổi nhân sự

Tính toán số lượng nhân viên thay đổi giữa hai thời điểm trong mỗi phòng ban.
Xem mã nguồn

#include 
using namespace std;

int main(){
    int soPhong, soThayDoi;
    cin >> soPhong >> soThayDoi;
    vector<int> truocDo(105, 0), sauDo(105, 0);
    
    for(int i=0; i> phongTruoc >> phongSau;
        truocDo[phongTruoc]++;
        sauDo[phongSau]++;
    }
    
    for(int i=1; i<=soThayDoi; ++i)
        cout << (sauDo[i] - truocDo[i]) << '\n';
    return 0;
}

Bài C - Quản lý cây con

Sử dụng cấu trúc dữ liệu heap tối thiểu để lưu trữ các giá trị và loại bỏ những phần tử nhỏ hơn hoặc bằng một ngưỡng nhất định.
Xem mã nguồn

#include 
using namespace std;

int main(){
    int soLenh;
    cin >> soLenh;
    priority_queue heap;
    
    while(soLenh--){
        int loai, giaTri;
        cin >> loai >> giaTri;
        if(loai == 1){
            heap.push(giaTri);
        }
        else{
            while(!heap.empty() && heap.top() <= giaTri){
                heap.pop();
            }
        }
        cout << heap.size() << '\n';
    }
    return 0;
}

Bài D - Số nguyên đặc biệt

Đếm số lượng số nguyên đặc biệt có thể tạo thành từ phép cộng lũy thừa của \(2\).
Xem mã nguồn

#include 
using namespace std;

long long noiLienKet(long long x, long long y){
    long long t = y;
    while(t){
        x *= 10;
        t /= 10;
    }
    return x + y;
}

void timKiemSau(long long x, vector<long long>& danhSach, set<long long>& tapHop){
    if(x <= 1e9){
        if(x != 0 && tapHop.find(x) == tapHop.end()){
            danhSach.push_back(x);
            tapHop.insert(x);
        }
    }
    else return;
    for(int i=0; i<30; ++i){
        timKiemSau(noiLienKet(x, pow(2, i)), danhSach, tapHop);
    }
}

int main(){
    int thuTu;
    cin >> thuTu;
    vector<long long> luuyThua;
    for(int i=0; pow(2, i) <= 1e9; ++i){
        luuyThua.push_back(pow(2, i));
    }
    
    vector<long long> cacSo;
    set<long long> daXet;
    timKiemSau(0, cacSo, daXet);
    sort(cacSo.begin(), cacSo.end());
    cout << cacSo[thuTu-1];
    return 0;
}

Bài E - Khoảng cách trên cây

Kiểm tra xem ma trận khoảng cách đã cho có biểu diễn được bởi một cây hợp lệ hay không.
Xem mã nguồn

#include 
using namespace std;

const int MAXN = 3005;
struct Canh {
    int u, v;
    long long w;
};

bool cmp(Canh a, Canh b) { return a.w < b.w; }

int cha[MAXN];
vector> ke[MAXN];
long long kc[MAXN], stt[MAXN][15], sau[MAXN];

int timCha(int x){
    if(x == cha[x]) return x;
    return cha[x] = timCha(cha[x]);
}

void dfs(int u, int p){
    sau[u] = sau[p] + 1;
    stt[u][0] = p;
    for(int j=1; j<14; ++j){
        stt[u][j] = stt[stt[u][j-1]][j-1];
    }
    for(auto &[v, w] : ke[u]){
        if(v == p) continue;
        kc[v] = kc[u] + w;
        dfs(v, u);
    }
}

int lca(int u, int v){
    if(sau[u] < sau[v]) swap(u, v);
    for(int j=13; j>=0; --j){
        if(sau[stt[u][j]] >= sau[v])
            u = stt[u][j];
    }
    if(u == v) return u;
    for(int j=13; j>=0; --j){
        if(stt[u][j] != stt[v][j]){
            u = stt[u][j];
            v = stt[v][j];
        }
    }
    return stt[u][0];
}

int main(){
    int n;
    cin >> n;
    vector<Canh> danhSachCanh;
    for(int i=1; i<=n; ++i){
        cha[i] = i;
        for(int j=i+1; j<=n; ++j){
            long long tmp;
            cin >> tmp;
            danhSachCanh.push_back({i, j, tmp});
        }
    }
    sort(danhSachCanh.begin(), danhSachCanh.end(), cmp);
    
    for(auto &c : danhSachCanh){
        int u = c.u, v = c.v;
        if(timCha(u) != timCha(v)){
            cha[timCha(u)] = timCha(v);
            ke[u].push_back({v, c.w});
            ke[v].push_back({u, c.w});
        }
    }
    
    dfs(1, 0);
    bool hopLe = true;
    for(int i=1; i<=n && hopLe; ++i){
        for(int j=i+1; j<=n && hopLe; ++j){
            if(kc[i] + kc[j] - 2 * kc[lca(i, j)] != danhSachCanh[(i-1)*n+j-1].w){
                hopLe = false;
            }
        }
    }
    cout << (hopLe ? "Yes" : "No");
    return 0;
}

Thẻ: C++ atcoder GraphTheory

Đăng vào ngày 5 tháng 6 lúc 16:20