Bài toán D - Hoán vị số chính phương

Đề bài yêu cầu tìm số lượng các số chính phương có đúng n chữ số, sao cho tần suất xuất hiện của các chữ số trong số đó khớp với tần suất trong chuỗi đã cho.

Giải pháp hiệu quả là duyệt qua tất cả các số chính phương có thể có. Vì n tối đa là 13, nên ta chỉ cần duyệt các cơ số từ 0 đến sqrt(10^13), tức là khoảng 316,227. Với mỗi số chính phương, ta đếm tần suất các chữ số và so sánh với tần suất trong chuỗi đầu vào. Lưu ý: số chính phương phải có đúng n chữ số, nếu ít hơn thì cần thêm các số 0 ở đầu.

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

using namespace std;

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

    int soChuSo;
    string chuoiSo;
    cin >> soChuSo >> chuoiSo;

    // Đếm tần suất các chữ số trong chuỗi đầu vào
    vector<int> demChuSoNhapVao(10, 0);
    for (char c : chuoiSo) {
        demChuSoNhapVao[c - '0']++;
    }

    long long demKetQuaHopLe = 0;
    long long coSoMax = 316228; // sqrt(10^13) + 1

    for (long long coSo = 0; coSo <= coSoMax; ++coSo) {
        long long soBinhPhuong = coSo * coSo;
        vector<int> demChuSoBinhPhuong(10, 0);

        // Đếm tần suất các chữ số của số chính phương
        long long temp = soBinhPhuong;
        int soChuSoHienTai = 0;
        while (temp > 0) {
            demChuSoBinhPhuong[temp % 10]++;
            temp /= 10;
            soChuSoHienTai++;
        }

        // Nếu số chính phương có ít hơn n chữ số, thêm số 0 ở đầu
        while (soChuSoHienTai < soChuSo) {
            demChuSoBinhPhuong[0]++;
            soChuSoHienTai++;
        }

        // So sánh tần suất chữ số
        bool hopLe = true;
        for (int i = 0; i < 10; ++i) {
            if (demChuSoBinhPhuong[i] != demChuSoNhapVao[i]) {
                hopLe = false;
                break;
            }
        }

        if (hopLe) {
            demKetQuaHopLe++;
        }
    }

    cout << demKetQuaHopLe << endl;
    return 0;
}

Bài toán F - Đường đi đẹp

Đây là một bài toán kinh điển về Phân tích Phân số 0/1 (01 Fractional Programming). Ta cần tìm giá trị lớn nhất của một phân số, trong đó tử số và mẫu số là tổng các giá trị trên các cạnh của một đường đi.

Cách tiếp cận là sử dụng tìm kiếm nhị phân trên giá trị X. Với mỗi giá trị X được thử, ta biến đổi bài toán thành kiểm tra xem có tồn tại đường đi từ đỉnh 1 đến đỉnh n sao cho tổng (giá_trị_cạnh - X * trọng_số_cạnh) là dương hay không. Bài toán biến đổi này có thể được giải quyết bằng thuật toán quy hoạch động hoặc thuật toán làm mềm (relaxation) trên đồ thị.

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

using namespace std;

const double EPSILON = 1e-9;
const int MAXN = 200005;

struct Canh {
    int dinhDen;
    double giaTri, trongSo;
};

int soDinh, soCanh;
vector<Canh> danhSachKe[MAXN];
double giaTriDuongDi[MAXN];

// Kiểm tra xem có tồn tại đường đi với tổng (giaTri - X * trongSo) > 0 hay không
bool kiemTra(double X) {
    fill(giaTriDuongDi, giaTriDuongDi + soDinh + 1, -1e18);
    giaTriDuongDi[1] = 0;

    // Thực hiện thuật toán Bellman-Ford để tìm đường đi dài nhất
    for (int i = 1; i < soDinh; ++i) {
        for (int u = 1; u <= soDinh; ++u) {
            if (giaTriDuongDi[u] < -1e15) continue; // Chỉ xét các đỉnh đã được cập nhật
            for (const Canh& c : danhSachKe[u]) {
                double giaTriMoi = giaTriDuongDi[u] + c.giaTri - X * c.trongSo;
                if (giaTriMoi > giaTriDuongDi[c.dinhDen]) {
                    giaTriDuongDi[c.dinhDen] = giaTriMoi;
                }
            }
        }
    }

    return giaTriDuongDi[soDinh] > EPSILON;
}

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

    cin >> soDinh >> soCanh;
    for (int i = 0; i < soCanh; ++i) {
        int u, v;
        double val, w;
        cin >> u >> v >> val >> w;
        danhSachKe[u].push_back({v, val, w});
    }

    double trai = 0, phai = 10000;
    while (phai - trai > EPSILON) {
        double giua = (trai + phai) / 2.0;
        if (kiemTra(giua)) {
            trai = giua;
        } else {
            phai = giua;
        }
    }

    cout << fixed << setprecision(10) << trai << endl;
    return 0;
}