Ta duyệt lần lượt từng phần tử a[i] và tính khoảng cách đến x là |a[i] — x|.

Gọi dapAn là đáp án đang tốt nhất. Ta thay dapAn nếu tìm được phần tử gần x hơn. Nếu khoảng cách bằng nhau, chọn giá trị nhỏ hơn theo yêu cầu đề bài.

Dùng long long khi tính hiệu để phép trừ vẫn an toàn với các số âm và dương lớn.

#include <iostream>
using namespace std;

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

    int soPhanTu;
    long long giaTriCanTim;
    cin >> soPhanTu >> giaTriCanTim;

    long long mang[1005];
    for (int chiSo = 0; chiSo < soPhanTu; chiSo++) {
        cin >> mang[chiSo];
    }

    long long dapAn = mang[0];
    long long khoangCachNhoNhat = dapAn - giaTriCanTim;
    if (khoangCachNhoNhat < 0) khoangCachNhoNhat = -khoangCachNhoNhat;

    for (int chiSo = 1; chiSo < soPhanTu; chiSo++) {
        long long khoangCach = mang[chiSo] - giaTriCanTim;
        if (khoangCach < 0) khoangCach = -khoangCach;

        if (khoangCach < khoangCachNhoNhat ||
            (khoangCach == khoangCachNhoNhat && mang[chiSo] < dapAn)) {
            dapAn = mang[chiSo];
            khoangCachNhoNhat = khoangCach;
        }
    }

    cout << dapAn << '\n';
    return 0;
}

Sau khi sắp xếp mảng tăng dần, hai số gần nhau nhất sẽ nằm cạnh nhau. Vì thế, ta chỉ cần duyệt các cặp a[i] và a[i + 1].

Với mỗi cặp, tính hiệu a[i + 1] — a[i]. Nếu khoảng cách nhỏ hơn đáp án hiện tại thì cập nhật. Nếu bằng nhau, so sánh hai đầu của cặp theo thứ tự từ điển: chọn cặp có số thứ nhất nhỏ hơn, hoặc nếu bằng nhau thì số thứ hai nhỏ hơn.

#include <algorithm>
#include <iostream>
using namespace std;

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

    int soPhanTu;
    cin >> soPhanTu;

    long long mang[100005];
    for (int chiSo = 0; chiSo < soPhanTu; chiSo++) {
        cin >> mang[chiSo];
    }

    sort(mang, mang + soPhanTu);

    long long khoangCachNhoNhat = mang[1] - mang[0];
    long long soTraiTotNhat = mang[0];
    long long soPhaiTotNhat = mang[1];

    for (int chiSo = 1; chiSo + 1 < soPhanTu; chiSo++) {
        long long khoangCach = mang[chiSo + 1] - mang[chiSo];

        if (khoangCach < khoangCachNhoNhat ||
            (khoangCach == khoangCachNhoNhat &&
             (mang[chiSo] < soTraiTotNhat ||
              (mang[chiSo] == soTraiTotNhat && mang[chiSo + 1] < soPhaiTotNhat)))) {
            khoangCachNhoNhat = khoangCach;
            soTraiTotNhat = mang[chiSo];
            soPhaiTotNhat = mang[chiSo + 1];
        }
    }

    cout << khoangCachNhoNhat << '\n';
    cout << soTraiTotNhat << ' ' << soPhaiTotNhat << '\n';
    return 0;
}

Với mỗi test, tính tổng số kẹo. Trung bình của lớp là tongKeo / soBan.

Để tránh số thực, ta so sánh a[i] với trung bình bằng phép nhân:

keo[i] < tongKeo / soBan tương đương keo[i] * soBan < tongKeo.

Duyệt mảng thêm một lần nữa để đếm số bạn có ít hơn trung bình và tìm số kẹo lớn nhất trong nhóm đó. Nếu nhóm rỗng, giữ đáp án lớn nhất bằng -1.

#include <iostream>
using namespace std;

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

    int soTest;
    cin >> soTest;

    while (soTest--) {
        int soBan;
        cin >> soBan;

        long long keo[10005];
        long long tongKeo = 0;

        for (int chiSo = 0; chiSo < soBan; chiSo++) {
            cin >> keo[chiSo];
            tongKeo += keo[chiSo];
        }

        int soBanItHonTrungBinh = 0;
        long long keoNhieuNhat = -1;

        for (int chiSo = 0; chiSo < soBan; chiSo++) {
            if (keo[chiSo] * soBan < tongKeo) {
                soBanItHonTrungBinh++;
                if (keo[chiSo] > keoNhieuNhat) {
                    keoNhieuNhat = keo[chiSo];
                }
            }
        }

        cout << soBanItHonTrungBinh << ' ' << keoNhieuNhat << '\n';
    }

    return 0;
}

Trong một bộ ba tạo thành tam giác vuông, cạnh huyền là cạnh dài nhất. Ta sắp xếp các thanh gỗ, sau đó lần lượt chọn một vị trí k làm cạnh huyền.

Với cạnh huyền a[k], cần tìm hai cạnh ở bên trái sao cho:

a[i] * a[i] + a[j] * a[j] = a[k] * a[k].

Đặt i ở đầu mảng và j ngay trước k. Nếu tổng bình phương còn nhỏ thì tăng i để lấy cạnh lớn hơn. Nếu tổng quá lớn thì giảm j để lấy cạnh nhỏ hơn.

Hai con trỏ này giúp ta kiểm tra một cạnh huyền trong một lượt duyệt thay vì thử mọi bộ ba.

#include <algorithm>
#include <iostream>
using namespace std;

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

    int soTest;
    cin >> soTest;

    while (soTest--) {
        int soThanh;
        cin >> soThanh;

        long long thanhGo[5005];
        for (int chiSo = 0; chiSo < soThanh; chiSo++) {
            cin >> thanhGo[chiSo];
        }

        sort(thanhGo, thanhGo + soThanh);

        bool daTimThay = false;

        for (int viTriCanhHuyen = soThanh - 1; viTriCanhHuyen >= 2 && !daTimThay; viTriCanhHuyen--) {
            int viTriTrai = 0;
            int viTriPhai = viTriCanhHuyen - 1;

            while (viTriTrai < viTriPhai) {
                long long tongBinhPhuong = thanhGo[viTriTrai] * thanhGo[viTriTrai] + thanhGo[viTriPhai] * thanhGo[viTriPhai];
                long long canhHuyenBinhPhuong = thanhGo[viTriCanhHuyen] * thanhGo[viTriCanhHuyen];

                if (tongBinhPhuong == canhHuyenBinhPhuong) {
                    daTimThay = true;
                    break;
                } else if (tongBinhPhuong < canhHuyenBinhPhuong) {
                    viTriTrai++;
                } else {
                    viTriPhai--;
                }
            }
        }

        if (daTimThay) {
            cout << "YASS\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

Ta sắp xếp mã số trước. Khi đó, các sinh viên có cùng mã số sẽ đứng cạnh nhau.

Với mỗi truy vấn X, dùng tìm kiếm nhị phân để tìm vị trí đầu tiên có giá trị không nhỏ hơn X. Nếu tại vị trí đó không phải X, mã số này không có trong hàng. Nếu tìm thấy, ta đếm tiếp các phần tử liên tiếp bằng X.

Vì đề đánh số vị trí từ 1, khi in vị trí đầu tiên ta cộng thêm 1.

#include <algorithm>
#include <iostream>
using namespace std;

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

    int soSinhVien, soTruyVan;
    cin >> soSinhVien >> soTruyVan;

    int maSinhVien[3005];
    for (int chiSo = 0; chiSo < soSinhVien; chiSo++) {
        cin >> maSinhVien[chiSo];
    }

    sort(maSinhVien, maSinhVien + soSinhVien);

    while (soTruyVan--) {
        int maCanTim;
        cin >> maCanTim;

        int trai = 0;
        int phai = soSinhVien;

        // Tìm vị trí đầu tiên mà maSinhVien[chiSo] >= maCanTim.
        while (trai < phai) {
            int giua = trai + (phai - trai) / 2;

            if (maSinhVien[giua] < maCanTim) {
                trai = giua + 1;
            } else {
                phai = giua;
            }
        }

        int viTriDau = trai;

        if (viTriDau == soSinhVien || maSinhVien[viTriDau] != maCanTim) {
            cout << -1 << '\n';
        } else {
            int soLuong = 0;
            int chiSo = viTriDau;

            while (chiSo < soSinhVien && maSinhVien[chiSo] == maCanTim) {
                soLuong++;
                chiSo++;
            }

            cout << viTriDau + 1 << ' ' << soLuong << '\n';
        }
    }

    return 0;
}

Ta thử một độ dài đoạn mì doDaiDoan. Bó mì dài a[i] cắt được doDaiBoMi[i] / doDaiDoan đoạn. Cộng số đoạn của tất cả các bó để biết độ dài đó có cắt được ít nhất k đoạn hay không.

Nếu độ dài doDaiDoan dùng được thì mọi độ dài nhỏ hơn cũng dùng được. Nếu không dùng được thì độ dài lớn hơn cũng không thể dùng được. Vì vậy, ta dùng tìm kiếm nhị phân trên đáp án, trong khoảng từ 1 đến bó mì dài nhất.

Nếu ngay cả độ dài 1 cũng không đủ k đoạn thì đáp án vẫn là 0.

#include <iostream>
using namespace std;

int soBoMi;
long long soDoanCanCat;
long long doDaiBoMi[100005];

bool catDuoc(long long doDaiDoan) {
    long long soDoanCatDuoc = 0;

    for (int chiSo = 0; chiSo < soBoMi; chiSo++) {
        soDoanCatDuoc += doDaiBoMi[chiSo] / doDaiDoan;
        if (soDoanCatDuoc >= soDoanCanCat) {
            return true;
        }
    }

    return false;
}

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

    cin >> soBoMi >> soDoanCanCat;

    long long doDaiLonNhat = 0;
    for (int chiSo = 0; chiSo < soBoMi; chiSo++) {
        cin >> doDaiBoMi[chiSo];
        if (doDaiBoMi[chiSo] > doDaiLonNhat) {
            doDaiLonNhat = doDaiBoMi[chiSo];
        }
    }

    long long trai = 1;
    long long phai = doDaiLonNhat;
    long long dapAn = 0;

    while (trai <= phai) {
        long long giua = trai + (phai - trai) / 2;

        if (catDuoc(giua)) {
            dapAn = giua;
            trai = giua + 1;
        } else {
            phai = giua - 1;
        }
    }

    cout << dapAn << '\n';
    return 0;
}

Nếu cộng lại từng phần tử cho mỗi truy vấn thì sẽ rất chậm khi có nhiều truy vấn. Ta tạo mảng cộng dồn tongCongDon:

• tongCongDon[i] là tổng các phần tử từ vị trí 1 đến vị trí i.
• Tổng từ l đến r bằng prefix[r] — prefix[l — 1].

Như vậy, mỗi truy vấn chỉ cần một phép trừ.

#include <iostream>
using namespace std;

long long tongCongDon[200005];

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

    int soPhanTu;
    cin >> soPhanTu;

    tongCongDon[0] = 0;
    for (int chiSo = 1; chiSo <= soPhanTu; chiSo++) {
        long long giaTri;
        cin >> giaTri;
        tongCongDon[chiSo] = tongCongDon[chiSo - 1] + giaTri;
    }

    int soTruyVan;
    cin >> soTruyVan;

    while (soTruyVan--) {
        int trai, phai;
        cin >> trai >> phai;
        cout << tongCongDon[phai] - tongCongDon[trai - 1] << '\n';
    }

    return 0;
}

Ta mô phỏng lượt chọn bánh. Ở mỗi lượt, người chơi so sánh điểm vị ngon của chiếc ngoài cùng bên trái và ngoài cùng bên phải, rồi lấy chiếc có điểm lớn hơn.

Dùng hai biến tổng riêng cho Nam Anh và Thế Vĩ. Sau mỗi lượt, bỏ chiếc bánh vừa lấy khỏi dãy bằng cách dịch con trỏ trái hoặc phải. Nếu hai đầu bằng nhau, code chọn đầu trái; hai chiếc có cùng điểm vị ngon nên cách chọn này giữ cho mô phỏng nhất quán.

Sau khi hết bánh, so sánh hai tổng để in tên người thắng hoặc kết quả hòa.

#include <iostream>
using namespace std;

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

    int soTest;
    cin >> soTest;

    while (soTest--) {
        int soBanh;
        cin >> soBanh;

        long long diemViNgon[100005];
        for (int chiSo = 0; chiSo < soBanh; chiSo++) {
            cin >> diemViNgon[chiSo];
        }

        int dauTrai = 0;
        int dauPhai = soBanh - 1;
        int luot = 0; // 0: Nam Anh, 1: Thế Vĩ
        long long tongNamAnh = 0;
        long long tongTheVi = 0;

        while (dauTrai <= dauPhai) {
            long long diemChon;

            if (diemViNgon[dauTrai] >= diemViNgon[dauPhai]) {
                diemChon = diemViNgon[dauTrai];
                dauTrai++;
            } else {
                diemChon = diemViNgon[dauPhai];
                dauPhai--;
            }

            if (luot == 0) {
                tongNamAnh += diemChon;
                luot = 1;
            } else {
                tongTheVi += diemChon;
                luot = 0;
            }
        }

        if (tongNamAnh > tongTheVi) {
            cout << "Nam Anh\n";
        } else if (tongTheVi > tongNamAnh) {
            cout << "Thế Vĩ\n";
        } else {
            cout << "Oẳn tù xì\n";
        }
    }

    return 0;
}

Gọi tongCongDon[i] là tổng năng lượng từ viên đá thứ 1 đến viên thứ i. Đoạn từ L đến R có tổng K khi:

prefix[R] — prefix[L — 1] = K

Hay nói cách khác, khi đang xét tongCongDon[R], ta cần đếm các tổng trước đó bằng prefix[R] — K.

Các viên đá có thể mang giá trị âm, nên ta không thể dừng sớm khi tổng vượt quá K. Ngoài ra, các tổng cộng dồn có thể rất lớn và âm. Vì vậy, ta làm như sau:

1. Tính toàn bộ các tổng cộng dồn.
2. Sao chép chúng sang mảng mangNen, sắp xếp và bỏ các giá trị trùng nhau.
3. Dùng tìm kiếm nhị phân để tìm vị trí của từng tổng trong mangNen.
4. Mảng tanSuat lưu số lần mỗi tổng đã xuất hiện trước đó.

Khi xét từng vị trí từ trái sang phải, ta cộng số lần đã gặp prefix[i] — K vào đáp án, rồi mới tăng tần số của tongCongDon[i]. Thứ tự này bảo đảm chỉ đếm những đoạn có độ dài lớn hơn 0.

#include <algorithm>
#include <iostream>
using namespace std;

const int GIOI_HAN = 200005;

long long tongCongDon[GIOI_HAN];
long long mangNen[GIOI_HAN];
int tanSuat[GIOI_HAN];

int timViTri(long long giaTri, int kichThuoc) {
    int trai = 0;
    int phai = kichThuoc - 1;

    while (trai <= phai) {
        int giua = trai + (phai - trai) / 2;

        if (mangNen[giua] == giaTri) {
            return giua;
        } else if (mangNen[giua] < giaTri) {
            trai = giua + 1;
        } else {
            phai = giua - 1;
        }
    }

    return -1;
}

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

    int soPhanTu;
    long long tongCanTim;
    cin >> soPhanTu >> tongCanTim;

    tongCongDon[0] = 0;
    for (int chiSo = 1; chiSo <= soPhanTu; chiSo++) {
        long long giaTri;
        cin >> giaTri;
        tongCongDon[chiSo] = tongCongDon[chiSo - 1] + giaTri;
    }

    for (int chiSo = 0; chiSo <= soPhanTu; chiSo++) {
        mangNen[chiSo] = tongCongDon[chiSo];
    }

    sort(mangNen, mangNen + soPhanTu + 1);

    int kichThuoc = 0;
    for (int chiSo = 0; chiSo <= soPhanTu; chiSo++) {
        if (chiSo == 0 || mangNen[chiSo] != mangNen[chiSo - 1]) {
            mangNen[kichThuoc] = mangNen[chiSo];
            kichThuoc++;
        }
    }

    for (int chiSo = 0; chiSo < kichThuoc; chiSo++) {
        tanSuat[chiSo] = 0;
    }

    int viTriTong0 = timViTri(0, kichThuoc);
    tanSuat[viTriTong0] = 1;

    long long dapAn = 0;

    for (int chiSo = 1; chiSo <= soPhanTu; chiSo++) {
        long long tongCanTimTaiViTri = tongCongDon[chiSo] - tongCanTim;
        int viTriCanTim = timViTri(tongCanTimTaiViTri, kichThuoc);

        if (viTriCanTim != -1) {
            dapAn += tanSuat[viTriCanTim];
        }

        int viTriHienTai = timViTri(tongCongDon[chiSo], kichThuoc);
        tanSuat[viTriHienTai]++;
    }

    cout << dapAn << '\n';
    return 0;
}

Mức năng lượng chỉ nằm trong khoảng từ 1 đến 100000, nên ta tạo mảng tần số tanSuat.

Mỗi lần đọc được a[i], tăng frequency[a[i]] lên 1. Sau đó duyệt các mức năng lượng tăng dần và tìm tần số lớn nhất. Khi tần số bằng nhau, ta không cập nhật lại đáp án; do đang duyệt từ nhỏ đến lớn nên đáp án nhỏ nhất sẽ được giữ lại.

#include <iostream>
using namespace std;

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

    int soPhanTu;
    cin >> soPhanTu;

    int tanSuat[100005] = {};

    for (int chiSo = 0; chiSo < soPhanTu; chiSo++) {
        int nangLuong;
        cin >> nangLuong;
        tanSuat[nangLuong]++;
    }

    int nangLuongNhieuNhat = 0;
    int tanSuatLonNhat = 0;

    for (int mucNangLuong = 1; mucNangLuong <= 100000; mucNangLuong++) {
        if (tanSuat[mucNangLuong] > tanSuatLonNhat) {
            tanSuatLonNhat = tanSuat[mucNangLuong];
            nangLuongNhieuNhat = mucNangLuong;
        }
    }

    cout << nangLuongNhieuNhat << ' ' << tanSuatLonNhat << '\n';
    return 0;
}

Có nhiều truy vấn và mỗi truy vấn hỏi số lượng số nguyên tố nhỏ hơn N. Ta sàng nguyên tố một lần đến giá trị lớn nhất trong các truy vấn.

Mảng laNguyenTo[x] cho biết x có phải số nguyên tố hay không. Ban đầu đánh dấu mọi số là nguyên tố, sau đó bỏ 0 và 1. Với mỗi số nguyên tố i, ta đánh dấu các bội lớn hơn của i là hợp số.

Cuối cùng tạo mảng cộng dồn primeCount. Kết quả cho truy vấn N là demNguyenTo[N — 1], vì đề hỏi các số nguyên tố nhỏ hơn N.

#include <iostream>
using namespace std;

const int GIOI_HAN = 1000005;

bool laNguyenTo[GIOI_HAN];
int demNguyenTo[GIOI_HAN];
int truyVan[100005];

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

    int soTruyVan;
    cin >> soTruyVan;

    int gioiHanLonNhat = 1;
    for (int chiSo = 0; chiSo < soTruyVan; chiSo++) {
        cin >> truyVan[chiSo];
        if (truyVan[chiSo] > gioiHanLonNhat) {
            gioiHanLonNhat = truyVan[chiSo];
        }
    }

    for (int chiSo = 0; chiSo <= gioiHanLonNhat; chiSo++) {
        laNguyenTo[chiSo] = true;
    }

    laNguyenTo[0] = false;
    if (gioiHanLonNhat >= 1) {
        laNguyenTo[1] = false;
    }

    for (int chiSo = 2; 1LL * chiSo * chiSo <= gioiHanLonNhat; chiSo++) {
        if (laNguyenTo[chiSo]) {
            for (int boi = chiSo * chiSo; boi <= gioiHanLonNhat; boi += chiSo) {
                laNguyenTo[boi] = false;
            }
        }
    }

    demNguyenTo[0] = 0;
    for (int chiSo = 1; chiSo <= gioiHanLonNhat; chiSo++) {
        demNguyenTo[chiSo] = demNguyenTo[chiSo - 1];
        if (laNguyenTo[chiSo]) {
            demNguyenTo[chiSo]++;
        }
    }

    for (int chiSo = 0; chiSo < soTruyVan; chiSo++) {
        int gioiHan = truyVan[chiSo];
        if (gioiHan <= 1) {
            cout << 0 << '\n';
        } else {
            cout << demNguyenTo[gioiHan - 1] << '\n';
        }
    }

    return 0;
}

Bài này có thể làm bằng mảng ký tự char[], chưa cần dùng string.

Ta chia dãy thành k đoạn, mỗi đoạn có n / k chữ cái. Với từng đoạn:

1. Đếm số lần xuất hiện của mỗi chữ cái bằng mảng frequency[26].
2. Xếp các chữ cái phân biệt theo tần số tăng dần. Nếu tần số bằng nhau, duyệt chữ cái từ a đến z để được thứ tự bảng chữ cái.
3. Mỗi chữ cái sẽ là một cột: nếu nó xuất hiện f lần thì in nó ở f dòng đầu tiên.

Các cột của các đoạn được ghép từ trái sang phải. Nếu cột không có ký tự ở một dòng nào đó, ta vẫn in một dấu cách để giữ cho các cột phía sau thẳng hàng. Giữa hai test case in một dòng trống, giống ví dụ của đề.

#include <iostream>
using namespace std;

const int GIOI_HAN = 1000005;

char dayKyTu[GIOI_HAN];
char kyTuCot[GIOI_HAN];
int chieuCaoCot[GIOI_HAN];

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

    int soTest;
    cin >> soTest;

    for (int boTest = 0; boTest < soTest; boTest++) {
        int soKyTu, soDoan;
        cin >> soKyTu >> soDoan;

        for (int viTri = 0; viTri < soKyTu; viTri++) {
            cin >> dayKyTu[viTri];
        }

        int doDaiDoan = soKyTu / soDoan;
        int soCot = 0;
        int chieuCaoLonNhat = 0;

        for (int batDau = 0; batDau < soKyTu; batDau += doDaiDoan) {
            int tanSuat[26] = {};

            for (int viTri = batDau; viTri < batDau + doDaiDoan; viTri++) {
                tanSuat[dayKyTu[viTri] - 'a']++;
            }

            // Tần số tăng dần; chữ cái tăng dần khi tần số bằng nhau.
            for (int soLan = 1; soLan <= doDaiDoan; soLan++) {
                for (int chuCai = 0; chuCai < 26; chuCai++) {
                    if (tanSuat[chuCai] == soLan) {
                        kyTuCot[soCot] = char('a' + chuCai);
                        chieuCaoCot[soCot] = soLan;
                        soCot++;

                        if (soLan > chieuCaoLonNhat) {
                            chieuCaoLonNhat = soLan;
                        }
                    }
                }
            }
        }

        if (boTest > 0) {
            cout << '\n';
        }

        for (int dong = 1; dong <= chieuCaoLonNhat; dong++) {
            for (int cot = 0; cot < soCot; cot++) {
                if (chieuCaoCot[cot] >= dong) {
                    cout << kyTuCot[cot];
                } else {
                    cout << ' ';
                }

                if (cot + 1 < soCot) {
                    cout << ' ';
                }
            }
            cout << '\n';
        }
    }

    return 0;
}