Tác giả yêu cầu kiểm tra xem trong dãy số có tồn tại ít nhất một bộ ba số liên tiếp bằng nhau hay không.

Giải pháp: Duyệt qua từng bộ ba số liên tiếp trong mảng và so sánh chúng.

Mã nguồn:

#include <iostream>
#include <vector>

using namespace std;

void kiemtraBaSoTuongDong(){
    int n;
    cin >> n;
    vector<int> mang(n);
    for(auto &x: mang) cin >> x;
    for(int i = 0; i < n - 2; ++i){
        if(mang[i] == mang[i+1] && mang[i] == mang[i+2]){
            cout << "Có" << endl;
            return;
        }
    }
    cout << "Không" << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    kiemtraBaSoTuongDong();
    return 0;
}

Tác giả cần quản lý một bộ thẻ với các phép toán thêm thẻ vào đỉnh và lấy thẻ từ đỉnh.

Giải pháp: Sử dụng ngăn xếp để thực hiện các phép toán.

Mã nguồn:

#include <iostream>
#include <stack>

using namespace std;

void quanLyThe(){
    int q;
    cin >> q;
    stack<int> nganXep;
    while(q--){
        int lenh;
        cin >> lenh;
        if(lenh == 1){
            int giaTri;
            cin >> giaTri;
            nganXep.push(giaTri);
        } else {
            cout << nganXep.top() << endl;
            nganXep.pop();
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    quanLyThe();
    return 0;
}

Tác giả cần tối ưu hóa việc mua quả sao cho tổng giá trị được thu về là lớn nhất.

Giải pháp: Sắp xếp các quả theo thứ tự giảm dần và chọn quả có giá trị không âm trước.

Mã nguồn:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void muaQua(){
    int den, trang;
    cin >> den >> trang;
    vector<int> mauDen(den), mauTrang(trang);
    for(auto &x: mauDen) cin >> x;
    for(auto &x: mauTrang) cin >> x;
    sort(mauDen.rbegin(), mauDen.rend());
    sort(mauTrang.rbegin(), mauTrang.rend());
    long long tong = 0;
    int i = 0, j = 0;
    while(i < den && mauDen[i] >= 0) tong += mauDen[i++];
    while(j < trang && j < i && mauTrang[j] >= 0) tong += mauTrang[j++];
    while(i < den && j < trang && mauDen[i] + mauTrang[j] >= 0){
        tong += mauDen[i++] + mauTrang[j++];
    }
    cout << tong << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    muaQua();
    return 0;
}

Tìm đường đi giữa các đỉnh của đồ thị sao cho tổng XOR của trọng số các cạnh trên đường đi là nhỏ nhất.

Giải pháp: Sử dụng thuật toán DFS để tìm tất cả các đường đi từ đỉnh xuất phát đến đỉnh đích.

Mã nguồn:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

const int MAX = 11;
vector<vector<pair<int, int>>> doThi(MAX);
bool tham[MAX];
long long ketQua = LLONG_MAX;

void timDuongDi(int dinhHienTai, int tongXOR){
    if(dinhHienTai == doThi.size() - 1){
        ketQua = min(ketQua, tongXOR);
        return;
    }
    tham[dinhHienTai] = true;
    for(auto &[dinhKe, trongSo]: doThi[dinhHienTai]){
        if(tham[dinhKe]) continue;
        timDuongDi(dinhKe, tongXOR ^ trongSo);
    }
    tham[dinhHienTai] = false;
}

void xuLyDuongDi(){
    int dinh, canh;
    cin >> dinh >> canh;
    doThi.resize(dinh + 1);
    for(int i = 0; i < canh; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        doThi[u].emplace_back(v, w);
        doThi[v].emplace_back(u, w);
    }
    tham[1] = true;
    timDuongDi(1, 0);
    cout << ketQua << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    xuLyDuongDi();
    return 0;
}

Xây dựng mảng A sao cho tổng XOR của các phần tử trong mỗi thành phần liên thông của đồ thị là cố định và tổng các phần tử của mảng A là nhỏ nhất.

Giải pháp: Sử dụng thuật toán DFS để xác định các thành phần liên thông và tính tổng XOR của mỗi thành phần.

Mã nguồn:

#include <iostream>
#include <vector>
#include <climits>
#include <cstring>

using namespace std;

const int MAX = 2e5 + 10;
vector<vector<pair<int, int>>> doThi(MAX);
int tong[MAX], a[MAX], bit[32];
bool tham[MAX];
bool hopLe = true;

void xacDinhThanhPhan(int dinhHienTai, int tongXOR){
    if(!hopLe) return;
    tong[dinhHienTai] = tongXOR;
    tham[dinhHienTai] = true;
    for(auto &[dinhKe, trongSo]: doThi[dinhHienTai]){
        if(tham[dinhKe]){
            if(tong[dinhKe] != (tongXOR ^ trongSo)){
                hopLe = false;
                return;
            }
        } else {
            xacDinhThanhPhan(dinhKe, tongXOR ^ trongSo);
        }
    }
}

void xayDungMangA(int dinhHienTai){
    tham[dinhHienTai] = true;
    for(auto &[dinhKe, trongSo]: doThi[dinhHienTai]){
        if(tham[dinhKe]) continue;
        a[dinhKe] = a[dinhHienTai] ^ trongSo;
        xayDungMangA(dinhKe);
    }
}

void xuLyTongGioihan(){
    int dinh, canh;
    cin >> dinh >> canh;
    doThi.resize(dinh + 1);
    for(int i = 0; i < canh; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        doThi[u].emplace_back(v, w);
        doThi[v].emplace_back(u, w);
    }
    for(int i = 1; i <= dinh; ++i){
        if(!tham[i]){
            hopLe = true;
            memset(bit, 0, sizeof(bit));
            xacDinhThanhPhan(i, 0);
            if(!hopLe){
                cout << "-1" << endl;
                return;
            }
            for(int j = 0; j < 32; ++j){
                if(bit[j] > dinh - bit[j]){
                    a[i] |= (1LL << j);
                }
            }
        }
    }
    memset(tham, 0, sizeof(tham));
    for(int i = 1; i <= dinh; ++i){
        if(!tham[i]){
            xayDungMangA(i);
        }
    }
    for(int i = 1; i <= dinh; ++i){
        cout << a[i] << " ";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    xuLyTongGioihan();
    return 0;
}

Tính số lượng cặp đảo ngược trong mảng khi nó được dịch chuyển theo cách cụ thể.

Giải pháp: Sử dụng cây nhị phân đánh dấu để hiệu quả đếm số lượng cặp đảo ngược.

Mã nguồn:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 2e5 + 10;
int cayNhiPhan[MAX];
int n, m, ketQua;

int lowBit(int x){
    return x & (-x);
}

int dem(int viTri){
    int tong = 0;
    for(; viTri; viTri -= lowBit(viTri)){
        tong += cayNhiPhan[viTri];
    }
    return tong;
}

void capNhat(int viTri, int giaTri){
    for(; viTri <= n; viTri += lowBit(viTri)){
        cayNhiPhan[viTri] += giaTri;
    }
}

void xuLyDaoNguocDaoNguoc(){
    cin >> n >> m;
    vector<pair<int, int>> daoNguoc;
    vector<vector<int>> viTri(m + 1);
    for(int i = 1; i <= n; ++i){
        int x;
        cin >> x;
        viTri[x].push_back(i);
        daoNguoc.emplace_back(x, i);
    }
    sort(daoNguoc.rbegin(), daoNguoc.rend());
    for(auto &[giaTri, viTriHienTai]: daoNguoc){
        ketQua += dem(viTriHienTai);
        capNhat(viTriHienTai, 1);
    }
    cout << ketQua << endl;
    for(int k = 1; k < m; ++k){
        int giaTri = m - k;
        for(int i = 0; i < viTri[giaTri].size(); ++i){
            ketQua += viTri[giaTri][i] - 1 - i;
            ketQua -= n - viTri[giaTri][i] - viTri[giaTri].size() + i + 1;
        }
        cout << ketQua << endl;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    xuLyDaoNguocDaoNguoc();
    return 0;
}