ICPC PTIT 2025 – VÒNG LUYỆN TẬP SỐ 2

Aug 11, 2025

Hi anh em, đây sẽ là series chia sẻ lời giải các contest ICPC Học viện Công nghệ Bưu chính Viễn thông Hà Nội (ICPC PTIT).

Lưu ý: Các hints và solutions trong bài viết có thể chưa phải là tối ưu nhất, do đó chỉ mang tính tham khảo. Và đừng quên là hãy thử tự suy nghĩ và làm thử trước khi xem solution nhé!

Bắt đầu thôi! 🤩

Problem A

Cho dãy số AA có NN phần tử. Hãy xác định xem có tồn tại một đa giác (không nhất thiết phải lồi) có độ dài các cạnh tương ứng là tập hợp AA hay không?

Gợi ý điều kiện cần và đủ: Một đa giác có N cạnh có tính chất: độ dài của cạnh dài nhất phải nhỏ hơn tổng của N – 1 cạnh còn lại.

Input:

Dòng đầu tiên là số lượng cạnh NN (1≤N≤1001≤N≤100).
Dòng tiếp theo gồm NN số nguyên AiAi (1≤Ai≤1001≤Ai≤100).

Output:

In ra Yes nếu tồn tại đa giác.
In ra No nếu không tồn tại đa giác.

Example:

Input	Output
`4` `1 5 3 8`	`Yes`
`4` `1 3 4 8`	`No`

Hint:

Tính tổng tất cả các phần tử trong AA.
Tìm phần tử lớn nhất.
Nếu phần tử lớn nhất nhỏ hơn tổng các phần tử còn lại ⇒⇒ In Yes.
Ngược lại, in No.

Solution:

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        ll s = 0, mx = 0, x;
        for (int i = 0; i < n; ++i)
        {
            cin >> x;
            s += x;
            mx = max(mx, x);
        }
        cout << ((n >= 3 && mx < s - mx) ? "Yes" : "No");
    }
    return 0;
}

Problem B

Cho dãy số AA có NN phần tử.

Cho dãy số BB ban đầu rỗng. Hãy thực hiện NN thao tác sau đây:

Ở bước thứ ii, thêm phần tử AiAi vào cuối của dãy BB, sau đó đảo ngược dãy BB.

Nhiệm vụ của bạn là xác định dãy số BB sau khi thực hiện NN thao tác.

Input:

Dòng đầu tiên là số nguyên dương NN (1≤N≤2⋅1051≤N≤2⋅105).
Dòng tiếp theo gồm NN số nguyên AiAi (0≤Ai≤1090≤Ai≤109).

Output:

In ra dãy số BB cuối cùng.

Example:

Input	Output
`3` `1 2 3`	`3 1 2`
`4` `1 2 3 4`	`4 2 1 3`

Giải thích test 1:

Sau bước 1: B = (1)
Sau bước 2: B = (1 2) →→ đảo ngược →→ (2 1)
Sau bước 3: B = (2 1 3) →→ đảo ngược →→ (3 1 2)

Hint

Ta có thể tối ưu bằng cách:

Duy trì một deque (hàng đợi hai đầu).
Với mỗi phần tử mới:
- Nếu lượt là chẵn: chèn vào đầu.
- Nếu lượt là lẻ: chèn vào cuối.
Cuối cùng, nếu tổng số thao tác là lẻ →→ đảo ngược kết quả.

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

const int MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
    {
        int n, x;
        cin >> n;
 
        deque<int> dq;
        for (int i = 1; i <= n; ++i)
        {
            cin >> x;
 
            if (i & 1)
                dq.emplace_back(x);
            else
                dq.emplace_front(x);
        }
 
        if (n & 1)
        {
            for (int i = n - 1; ~i; --i)
                cout << dq[i] << ' ';
        }
        else
        {
            for (int& i : dq)
                cout << i << ' ';
        }
    }
    return 0;
}

Problem C

Cánh đồng của nông dân John gồm nhiều thửa ruộng. Mỗi thửa ruộng là một đa giác khép kín, được bao quanh bởi các hàng rào (đoạn thẳng), và chỉ giao nhau tại các đỉnh chung là đầu mút.

Ngoài yếu tố diện tích, anh John quan tâm tới yếu tố năng suất, được anh quy đổi theo tỉ lệ thuận 1:11:1 với bình phương diện tích của mỗi thửa ruộng.

Các bạn hãy giúp anh John tính tổng năng suất trên tất cả các thửa ruộng?

Input:

Dòng đầu là số nguyên NN (3≤N≤10003≤N≤1000), là số lượng các hàng rào.
NN dòng tiếp theo, mỗi dòng gồm 4 số nguyên x1,y1,x2,y2x1,y1,x2,y2 (0≤xi,yi≤10000≤xi,yi≤1000) mô tả một hàng rào (đoạn thẳng).

Input đảm bảo rằng:

Không có hai đoạn nào cắt nhau.

Tất cả đoạn đều cần thiết để tạo thành các thửa ruộng.

Toàn bộ hệ thống hàng rào là đồ thị phẳng, liên thông, không có cầu.

Output:

In ra một số thực là tổng năng suất của cả cánh đồng, với độ chính xác 6 chữ số sau dấu phẩy.

Example:

Input	Output
`4` `0 0 0 1` `0 1 1 1` `0 0 2 0` `1 1 2 0`	`2.250000`
`6` `0 0 0 1` `0 1 1 1` `0 0 1 0` `1 0 2 0` `1 1 2 0` `1 0 1 1`	`1.250000`
`16` `5 1 6 2` `5 4 6 2` `2 2 5 4` `2 2 4 5` `2 6 4 5` `2 6 6 7` `6 7 8 4` `8 4 8 6` `8 6 10 4` `10 4 10 7` `10 7 11 4` `10 1 11 4` `8 1 10 1` `5 1 8 1` `6 2 8 4` `10 1 10 4`	`390.250000`

Hint

Mỗi đoạn thẳng tạo thành một cạnh của đồ thị phẳng.
Với mỗi đoạn, xây dựng hai cung có hướng (đi xuôi và ngược) kèm góc phương vị.
Duyệt qua tất cả các cạnh chưa được thăm theo hướng ngược chiều kim đồng hồ để tìm các mặt (face) thực sự đại diện cho các thửa ruộng.
Áp dụng công thức diện tích đa giác:S=12∣∑i=1n(xiyi+1−xi+1yi)∣S=21∣∣i=1∑n(xiyi+1−xi+1yi)∣∣
Với mỗi mặt có diện tích S>0S>0, cộng S2S2 vào tổng năng suất.

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
using ld = long double;
#define endl '\n'

const int MOD = 1e9 + 7;

struct P
{
    double x, y;
};

struct E
{
    int a, b, rev;
    double ang;
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<P> p;
        map<pair<int, int>, int> myMap;
        auto get = [&](int x, int y)
        {
            auto k = make_pair(x, y);
            auto it = myMap.find(k);
            if (it != myMap.end())
                return it->second;
            int v = p.size();
            myMap[k] = v;
            p.push_back({(double)x, (double)y});
            return v;
        };
        vector<E> e;
        vector<vector<int>> adj;
        adj.reserve(n << 1);
        for (int i = 0; i < n; ++i)
        {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            int u = get(x1, y1), v = get(x2, y2);
            if ((int)adj.size() < (int)p.size())
                adj.resize(p.size());
            E e1{u, v, (int)e.size() + 1, atan2(p[v].y - p[u].y, p[v].x - p[u].x)};
            E e2{v, u, (int)e.size(), atan2(p[u].y - p[v].y, p[u].x - p[v].x)};
            e.emplace_back(e1);
            e.emplace_back(e2);
            adj[u].emplace_back(e.size() - 2);
            adj[v].emplace_back(e.size() - 1);
        }
        int m = e.size();
        for (int v = 0; v < adj.size(); ++v)
        {
            auto& a = adj[v];
            sort(a.begin(), a.end(), [&](int i, int j)
                 { return e[i].ang < e[j].ang; });
        }
        vector<int> nxt(m);
        for (int v = 0; v < adj.size(); ++v)
        {
            auto& a = adj[v];
            int s = a.size();
            for (int i = 0; i < s; ++i)
            {
                int idx1 = a[i];
                int idx2 = a[(i - 1 + s) % s];
                nxt[e[idx1].rev] = idx2;
            }
        }
        vector<bool> visited(m, false);
        double ans = 0;
        vector<int> f;
        for (int i = 0; i < m; ++i)
            if (!visited[i])
            {
                f.clear();
                int cur = i;
                while (!visited[cur])
                {
                    visited[cur] = true;
                    f.emplace_back(e[cur].a);
                    cur = nxt[cur];
                }
                double tmp = 0;
                int k = f.size();
                for (int j = 0; j < k; ++j)
                {
                    P A = p[f[j]], B = p[f[(j + 1) % k]];
                    tmp += A.x * B.y - B.x * A.y;
                }
                tmp *= 0.5;
                if (tmp > 0)
                    ans += tmp * tmp;
            }
        cout << fixed << setprecision(6) << ans << endl;
    }
    return 0;
}

Problem D

Một nhà hàng hiện đại có các món thức ăn chuyển động theo dây chuyền. Có tất cả NN vị trí chỗ ngồi, đánh dấu từ 1,2,…,N1,2,…,N. Vì nhà hàng rất nổi tiếng, nhiều đoàn khách tới cần phải đúng giờ và có đủ slot trống thì nhà hàng mới phục vụ.

Trong một ngày nọ, có MM sự kiện diễn ra, thuộc 1 trong 2 nhóm như sau:

Một đoàn có KiKi khách đến và họ muốn ngồi liền kề nhau. Nhân viên phục vụ muốn xếp nhóm này vào một dãy liên tiếp KiKi ghế trống. Nếu có thể, nhóm được xếp vào vị trí thấp nhất trong dãy ghế. Nếu không thể, nhóm khách sẽ bị từ chối phục vụ.
Các khách ở vị trí ghế từ AiAi đến BiBi đã ăn xong và họ rời đi, những vị trí còn lại sẽ trở thành ghế trống.

Nhiệm vụ của bạn là đếm số lượng đoàn khách bị từ chối phục vụ trong ngày?

Input:

Dòng đầu tiên là hai số nguyên dương NN và MM (1≤N,M≤5⋅1051≤N,M≤5⋅105).
MM dòng tiếp theo, mỗi dòng mô tả một sự kiện theo thứ tự thời gian tăng dần:
- Sự kiện loại 1: A K là có một đoàn KK khách tới nhà hàng.
- Sự kiện loại 2: L a b là tất cả các khách từ vị trí [a,b][a,b] sẽ rời đi.

Output:

In ra một số nguyên là số lượng nhóm khách bị từ chối.

Example:

Input	Output
`12 4` `A 6` `L 2 5` `A 7` `A 3`	`1`
`10 10` `L 2 9` `A 2` `L 3 4` `L 4 9` `A 11` `L 5 6` `L 2 5` `A 3` `A 10` `A 1`	`2`

Giải thích test 1:

Sự kiện 1: [1 1 1 1 1 1 0 0 0 0 0 0]
Sự kiện 2: [1 0 0 0 1 1 0 0 0 0 0 0]
Sự kiện 3: Không đủ chỗ, nhóm khách bị từ chối.
Sự kiện 4: [1 1 0 0 1 1 1 0 0 0 0 0]

Hint

Bài toán yêu cầu bạn xử lý hai loại sự kiện động trên một dãy ghế có trạng thái “trống” hoặc “đã ngồi”. Cần hỗ trợ:

Tìm đoạn liên tiếp dài ít nhất KK chỗ trống (cho khách ngồi).
Đánh dấu đoạn đã ngồi hoặc trả lại thành trống (sau khi rời đi).

Đây là bài toán quản lý đoạn liên tiếp điển hình, cần một cấu trúc dữ liệu mạnh để đảm bảo thời gian xử lý tốt (vì MM có thể tới 5⋅1055⋅105).

Giải pháp: Segment Tree với Lazy Propagation (Đọc thêm tại Cây Phân Đoạn (Segment Tree) “Vỡ Lòng”)

Dùng Segment Tree để quản lý đoạn ghế trống, với mỗi node lưu:

Biến	Ý nghĩa
`pfx[o]`	Số lượng ghế trống liên tiếp từ đầu đoạn mà node oo quản lý
`sfx[o]`	Số lượng ghế trống liên tiếp từ cuối đoạn
`bst[o]`	Độ dài đoạn ghế trống liên tiếp dài nhất trong node
`lz[o]`	Lazy propagation: nếu bằng 1 thì cả đoạn là trống, nếu 0 thì cả đoạn là bận

Ý tưởng xử lý:

Sự kiện A K (một nhóm KK khách đến):

Gọi query(1, 1, N, K) để tìm vị trí bắt đầu của đoạn ghế trống dài ít nhất KK.
Nếu không tồn tại đoạn phù hợp, tăng biến ans (đếm nhóm bị từ chối).
Nếu tìm được, gọi update() để đánh dấu đoạn từ i đến i + K - 1 là đã ngồi (ghế bận).

Sự kiện L a b (trả lại chỗ từ aa đến bb):

Gọi upd(1, 1, N, a, b, 1) để đánh dấu đoạn này là trống.

Tại sao cần dùng segment tree?

Cần truy vấn nhanh đoạn có KK ghế trống liên tiếp.
Cần cập nhật trạng thái của cả một đoạn (bận hoặc trống).
Với segment tree có lazy propagation:
- Truy vấn và cập nhật đều có độ phức tạp O(log⁡N)O(logN).
- Phù hợp với N,MN,M lên tới 5⋅1055⋅105.

Mô phỏng đơn giản: Giả sử ban đầu tất cả ghế trống: [0 0 0 0 0 0]

Sự kiện A 3: Tìm đoạn 000 và đánh dấu [1 1 1 0 0 0]

Sự kiện L 2 3: Trả lại ghế 2 và 3 →→ [1 0 0 0 0 0]

Sự kiện A 4: Tìm 0000 từ vị trí 2 →→ đánh dấu [1 1 1 1 0 0]

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

const int MOD = 1e9 + 7;

int n, m, ans;
int pfx[2000005], sfx[2000005], bst[2000005], lz[2000005];

void build(int o, int l, int r)
{
    lz[o] = -1;
    pfx[o] = sfx[o] = bst[o] = r - l + 1;
    if (l == r) return;
    int m = (l + r) >> 1;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
}

void apply(int o, int l, int r, int v)
{
    lz[o] = v;
    if (v)
        pfx[o] = sfx[o] = bst[o] = r - l + 1;
    else
        pfx[o] = sfx[o] = bst[o] = 0;
}

void push(int o, int l, int r)
{
    if (lz[o] != -1)
    {
        int m = (l + r) >> 1;
        apply(o << 1, l, m, lz[o]);
        apply(o << 1 | 1, m + 1, r, lz[o]);
        lz[o] = -1;
    }
}

void pull(int o, int l, int r)
{
    int m = (l + r) >> 1, lc = o << 1, rc = o << 1 | 1;
    pfx[o] = pfx[lc] == m - l + 1 ? pfx[lc] + pfx[rc] : pfx[lc];
    sfx[o] = sfx[rc] == r - m ? sfx[rc] + sfx[lc] : sfx[rc];
    bst[o] = max({bst[lc], bst[rc], sfx[lc] + pfx[rc]});
}

void update(int o, int l, int r, int ql, int qr, int v)
{
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr)
    {
        apply(o, l, r, v);
        return;
    }
    push(o, l, r);
    int m = (l + r) >> 1;
    update(o << 1, l, m, ql, qr, v);
    update(o << 1 | 1, m + 1, r, ql, qr, v);
    pull(o, l, r);
}

int query(int o, int l, int r, int k)
{
    if (bst[o] < k) return -1;
    if (l == r) return l;
    push(o, l, r);
    int m = (l + r) >> 1;
    if (bst[o << 1] >= k) return query(o << 1, l, m, k);
    if (sfx[o << 1] + pfx[o << 1 | 1] >= k) return m - sfx[o << 1] + 1;
    return query(o << 1 | 1, m + 1, r, k);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    fill(lz, lz + 4 * n, -1);
    build(1, 1, n);
    while (m--)
    {
        char c;
        cin >> c;
        if (c == 'A')
        {
            int k;
            cin >> k;
            int i = query(1, 1, n, k);
            if (i < 0) ++ans;
            else update(1, 1, n, i, i + k - 1, 0);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            update(1, 1, n, l, r, 1);
        }
    }
    cout << ans;
    return 0;
}

Problem E

Cho dãy số AA gồm NN phần tử và một số nguyên dương KK. Hãy đếm số dãy con khác rỗng trong AA sao cho không có hai phần tử nào trong dãy con này có giá trị tuyệt đối hiệu của chúng bằng đúng KK.

Vì kết quả có thể rất lớn, hãy in ra đáp án modulo 998244353998244353.

Input:

Dòng đầu là số lượng bộ test TT (1≤T≤1001≤T≤100).
Mỗi test bắt đầu bởi hai số nguyên NN và KK (1≤N≤2⋅1051≤N≤2⋅105, 1≤K≤1091≤K≤109).
Dòng thứ hai của mỗi test gồm NN số nguyên AiAi (1≤Ai≤1091≤Ai≤109).

Output:

Với mỗi test, in ra số lượng dãy con tìm được trên một dòng.

Example:

Input	Output
`3` `3 3` `3 6 9` `1 100` `4` `4 2` `2 4 7 9`	`4` `1` `8`

Giải thích test 3: Có 8 tập thỏa mãn là (2), (4), (7), (9), (2 7), (4 9), (4 7), (2 9)

Hint

Nếu không có ràng buộc nào, thì một tập con có nn phần tử sẽ có 2n−12n−1 tập con khác rỗng.
Nhưng ràng buộc ở đây là: không có cặp nào có hiệu tuyệt đối bằng đúng KK.
Để xử lý:
1. Đếm số lần xuất hiện của từng phần tử: cnt[x].
2. Xét từng chuỗi số dạng x,x+K,x+2K,…x,x+K,x+2K,… (tức là các dãy cách đều nhau bởi KK).
3. Với mỗi chuỗi:
  - Nếu phần tử trước đó (x−K)(x−K) không tồn tại, ta bắt đầu từ xx.
  - Duyệt các phần tử trong chuỗi theo thứ tự tăng, mỗi bước:
    - Gọi dp0 là số cách chọn các phần tử trước mà không chọn phần tử hiện tại.
    - Gọi dp1 là số cách chọn có phần tử hiện tại (phải không chọn phần tử trước đó).
  - Cập nhật bằng quy tắc động như:
    - new_dp0=dp0+dp1new_dp0=dp0+dp1
    - new_dp1′=dp0∗(2cnt[x]−1)new_dp1′=dp0∗(2cnt[x]−1)
4. Vì mỗi chuỗi là độc lập, nên ta tính kết quả bằng cách nhân số cách với nhau.

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

const int MOD = 998244353;

int addMod(int a, int b)
{
    int s = a + b;
    return s >= MOD ? s - MOD : s;
}

int subMod(int a, int b)
{
    int s = a - b;
    return s < 0 ? s + MOD : s;
}

int mulMod(ll a, ll b)
{
    return int((a * b) % MOD);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int pwr[200005];
    pwr[0] = 1;
    for (int i = 1; i < 200005; ++i)
        pwr[i] = addMod(pwr[i - 1], pwr[i - 1]);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        ll k;
        cin >> n >> k;
        unordered_map<ll, int> cnt;
        cnt.reserve(n << 1);
        for (int i = 0; i < n; ++i)
        {
            ll x;
            cin >> x;
            ++cnt[x];
        }

        vector<ll> val;
        val.reserve(cnt.size());
        for (auto& p : cnt)
            val.emplace_back(p.first);
        sort(val.begin(), val.end());

        int ans = 1;
        for (ll x : val)
        {
            if (cnt.find(x - k) != cnt.end())
                continue;

            int dp0 = 1;
            int dp1 = subMod(pwr[cnt[x]], 1);
            ll y = x + k;

            while (cnt.find(y) != cnt.end())
            {
                int c = cnt[y];
                int ndp0 = addMod(dp0, dp1);
                int ndp1 = mulMod(dp0, subMod(pwr[c], 1));
                dp0 = ndp0;
                dp1 = ndp1;
                y += k;
            }

            ans = mulMod(ans, addMod(dp0, dp1));
        }

        ans = subMod(ans, 1);
        cout << ans << endl;
    }
    return 0;
}

Problem F

Cho NN chai soda. Chai thứ ii hiện chứa AiAi đơn vị soda và có dung tích tối đa là BiBi (Ai≤BiAi≤Bi). Cần thực hiện thao tác đổ soda giữa các chai để dồn toàn bộ lượng soda hiện có vào số lượng chai ít nhất có thể.

Mục tiêu:

Sử dụng ít chai nhất (gọi là KK chai).
Trong số các cách đạt được KK chai, hãy chọn cách tốn ít thời gian nhất (gọi là TT).
Biết rằng việc đổ XX đơn vị soda từ một chai sang chai khác mất XX giây.

Lưu ý:

Lượng soda trong mỗi chai sau khi đổ không được vượt quá dung tích BiBi.

Tổng lượng soda ban đầu được bảo toàn.

Input:

Dòng đầu tiên chứa số nguyên dương NN (1≤N≤1001≤N≤100): số lượng chai.
Dòng thứ hai gồm NN số nguyên AiAi (1≤Ai≤1001≤Ai≤100): lượng soda còn lại trong chai thứ ii.
Dòng thứ ba gồm NN số nguyên BiBi (1≤Bi≤1001≤Bi≤100): dung tích của chai thứ ii.

Output:

In ra hai số nguyên KK và TT, trong đó KK là số lượng chai tối thiểu có thể chứa tất cả soda, và TT là thời gian tối thiểu để dồn soda vào KK chai đó.

Example:

Input	Output
`4` `2 4 4 3` `5 7 6 4`	`2 5`
`2` `1 1` `99 99`	`1 1`
`10` `18 42 5 1 26 8 40 34 8 29` `18 71 21 67 38 13 99 37 47 76`	`3 100`

Giải thích test 1:

Đổ chai thứ nhất sang chai thứ hai (mất 2 giây),
Đổ từ chai thứ tư 2 đơn vị sang chai thứ ba và 1 đơn vị sang chai thứ hai (3 giây),
Tổng: 5 giây. Chỉ cần 2 chai để chứa toàn bộ soda.

Hint

Gọi tổng lượng soda là S=∑AiS=∑Ai.
Sắp xếp BiBi giảm dần, cộng dồn từ lớn nhất đến khi tổng ≥S≥S, ta tìm được số chai tối thiểu KK.
Bây giờ cần chọn ra KK chai có tổng dung tích ≥S≥S sao cho:
- Soda dồn vào các chai đó là nhiều nhất (tức là đổ đi ít nhất).
- Dùng kỹ thuật quy hoạch động kiểu Knapsack (balo – Có thể tham khảo ví dụ 2 tại Nhập Môn Quy Hoạch Động Cơ Bản):
  - Duyệt qua tất cả tập con KK chai, dùng mảng dp[k][c] để lưu lượng soda tối đa có thể đưa vào tổng dung tích cc.
Thời gian T=S−mT=S−m, với mm là lượng soda đã đưa vào KK chai mục tiêu.

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    int a[n], b[n];
    int S = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        S += a[i];
    }
    for (int i = 0; i < n; ++i)
        cin >> b[i];

    vector<int> sb(b, b + n);
    sort(sb.begin(), sb.end(), greater<int>());

    int k = 0, sum = 0;
    while (sum < S)
        sum += sb[k++];

    int C = sum;
    const int INF = 2e9;
    vector<vector<int>> dp(k + 1, vector<int>(C + 1, -INF));
    dp[0][0] = 0;

    for (int i = 0; i < n; ++i)
    {
        int bi = b[i], ai = a[i];
        for (int j = min(k, i + 1); j >= 1; --j)
            for (int c = C; c >= bi; --c)
                dp[j][c] = max(dp[j][c], dp[j - 1][c - bi] + ai);
    }

    int m = 0;
    for (int c = S; c <= C; ++c)
        m = max(m, dp[k][c]);

    cout << k << ' ' << S - m;
    
    return 0;
}

Problem G

Số Lucas được định nghĩa theo công thức đệ quy như sau:

L0=2L0=2
L1=1L1=1
Li=Li−1+Li−2Li=Li−1+Li−2 (với i≥2i≥2)

Nhiệm vụ của bạn là xác định số Lucas thứ NN.

Input:

Một số nguyên NN duy nhất (1≤N≤861≤N≤86)

Output:

In ra số nguyên là số Lucas thứ NN.

Example:

Input	Output
`5`	`11`
`20`	`15127`

Hint

Đây là một chuỗi giống như Fibonacci nhưng với hai giá trị khởi đầu khác: L0=2L0=2, L1=1L1=1.
Tính toán bằng cách dùng biến tạm (không cần mảng) do mỗi testcase chỉ tính 1 lần.
Dùng vòng lặp từ 2 đến NN để cập nhật dần Li=Li−1+Li−2Li=Li−1+Li−2.

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    if (n == 0)
        cout << 2;
    else if (n == 1)
        cout << 1;
    else
    {
        long long p = 2, q = 1, r;
        for (int i = 2; i <= n; ++i)
        {
            r = p + q;
            p = q;
            q = r;
        }
        cout << q;
    }
}

Problem H

Lớp học Cấu trúc dữ liệu & Giải thuật có NN sinh viên, trong đó có một số nhóm sinh viên chơi thân với nhau.
Nếu XX và YY là bạn, YY và ZZ là bạn, theo tính chất bắc cầu, XX và ZZ cũng là bạn.

Để tránh việc trao đổi bài, các thầy cô đã sắp xếp phòng thi cho các bạn sinh viên sao cho không có bất kỳ 2 sinh viên nào là bạn của nhau ở cùng một phòng.
Các bạn hãy thử tính xem các thầy cô cần sử dụng ít nhất bao nhiêu phòng thi?

Input:

Dòng đầu tiên chứa hai số nguyên NN và MM (N,M≤200000N,M≤200000).
MM dòng tiếp theo, mỗi dòng gồm 2 số nguyên AiAi và BiBi, cho biết AiAi và BiBi là bạn của nhau (Ai≠BiAi=Bi).

Output:

In ra một số nguyên duy nhất là số phòng thi ít nhất cần sử dụng.

Example:

Input	Output
`5 3` `1 3` `2 4` `5 1`	`3`
`8 4` `2 1` `4 1` `5 8` `3 6`	`3`

Giải thích test 1:

Chia sinh viên thành các nhóm bạn:

Nhóm 1: (1, 3, 5)
Nhóm 2: (2, 4)
Nhóm 3: (5) đã vào rồi

Tổng cộng cần 3 phòng thi vì mỗi nhóm bạn cần phòng riêng.

Hint

Đây là bài toán tìm số thành phần liên thông trong đồ thị vô hướng.
Mỗi sinh viên là 1 đỉnh, mỗi cặp bạn bè là 1 cạnh.
Các nhóm bạn là các thành phần liên thông →→ cần tách nhau ra phòng thi.
Giải bằng Disjoin Set Union (DSU) để gộp nhóm bạn:
- Ban đầu mỗi sinh viên là 1 nhóm.
- Duyệt các cặp bạn, gộp nhóm lại.
Cuối cùng đếm số nhóm độc lập (tức là số đại diện không bị gộp vào nhóm khác).

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

int findRoot(vector<int>& root, int x)
{
    return root[x] == x ? x : root[x] = findRoot(root, root[x]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        vector<int> root(n + 1), sz(n + 1, 1);
        for (int i = 1; i <= n; ++i)
            root[i] = i;
        int ans = 1;
        while (m--)
        {
            int u, v;
            cin >> u >> v;
            int rootU = findRoot(root, u), rootV = findRoot(root, v);
            if (rootU != rootV)
            {
                root[rootV] = rootU;
                sz[rootU] += sz[rootV];
                ans = max(ans, sz[rootU]);
            }
        }
        cout << ans;
    }
    return 0;
}

Problem I

Cho ba số nguyên AA, BB và KK. Trong các xâu có độ dài đúng bằng A+BA+B, gồm AA ký tự a và BB ký tự b, hãy tìm xâu có thứ tự từ điển đúng bằng KK.

Input

Một dòng gồm 3 số nguyên AA, BB và KK (1≤A,B≤301≤A,B≤30, 1≤K≤S1≤K≤S).
SS là số lượng xâu có AA ký tự a và BB ký tự b.
KK đảm bảo không vượt quá phạm vi của số nguyên 64 bit.

Output

In ra xâu thứ KK trong thứ tự từ điển.

Example

Input	Output
`2 2 4`	`baab`
`2 2 6`	`bbaa`
`26 26 371326006850843`	`babbbbbaaaaabbbaabbabbbbbbaaabaababbaaababbaaabaaaab`

Giải thích test 1 và 2:

Thứ tự các xâu lần lượt là: aabb, abab, abba, baab, baba, bbaa.

Hint

Tổng số xâu hợp lệ là tổ hợp CA+BACA+BA.
Với mỗi ký tự đầu tiên:
- Nếu ta chọn a, thì còn lại cần tạo A−1A−1 ký tự a và BB ký tự b ⇒⇒ có CA+B−1A−1CA+B−1A−1 xâu như vậy.
- Nếu K≤CA+B−1A−1K≤CA+B−1A−1, thì ký tự đầu tiên là a.
- Ngược lại, ký tự đầu tiên là b thì ta trừ đi số lượng xâu bắt đầu bằng a.
Lặp lại quá trình này cho đến khi xâu được hình thành đầy đủ.

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int a, b;
    unsigned long long k;
    cin >> a >> b >> k;
    int n = a + b;

    unsigned long long C[65][65];
    for (int i = 0; i <= n; ++i)
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }

    string s;
    while (a > 0 || b > 0)
    {
        if (a == 0)
        {
            s += 'b';
            --b;
        }
        else if (b == 0)
        {
            s += 'a';
            --a;
        }
        else
        {
            unsigned long long cnt = C[a + b - 1][a - 1];
            if (k <= cnt)
            {
                s += 'a';
                --a;
            }
            else
            {
                s += 'b';
                k -= cnt;
                --b;
            }
        }
    }
    cout << s;
    return 0;
}

Problem J

Một bộ ba số (a,b,c)(a,b,c) được gọi là bộ ba số Pytago nếu:

a2=b2+c2a2=b2+c2

Người ta mở rộng khái niệm này, gọi là “siêu Pytago”, nếu thỏa mãn:

2a2=b2+c22a2=b2+c2

với điều kiện aa, bb, cc đôi một khác nhau.

Input:

Gồm một số nguyên dương aa duy nhất (1≤a≤1051≤a≤105).

Output:

In ra YES nếu tồn tại bb và cc khác nhau sao cho 2a2=b2+c22a2=b2+c2, ngược lại in NO.

Example:

Input	Output
`2`	`NO`
`1005`	`YES`

Hint

Gọi T=2a2T=2a2, ta cần kiểm tra xem có tồn tại hai số nguyên dương b≠ab=a, c≠ac=a sao cho b2+c2=Tb2+c2=T.
Vì 1≤a,b,c≤1051≤a,b,c≤105, nên ta có thể áp dụng hai con trỏ (two pointers):
1. Duyệt bb từ 1 tăng lên.
2. Duyệt cc từ ⌊T⌋⌊T⌋ giảm xuống.
3. Bỏ qua nếu b=ab=a hoặc c=ac=a.
4. Nếu b2+c2==Tb2+c2==T →→ in YES.
5. Nếu nhỏ hơn →→ tăng bb, nếu lớn hơn →→ giảm cc.

Solution

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")

using namespace std;

using ll = long long;
#define endl '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll a;
    cin >> a;
    ll t = 2LL * a * a;
    ll l = 1, r = min(100000LL, (ll)sqrt(t));
    
    while (l < r)
    {
        if (l == a)
        {
            ++l;
            continue;
        }
        if (r == a)
        {
            --r;
            continue;
        }

        ll s = l * l + r * r;
        if (s == t)
        {
            cout << "YES";
            return 0;
        }
        if (s < t)
            ++l;
        else
            --r;
    }
    cout << "NO";
    return 0;
}

Nguồn: https://viblo.asia/p/icpc-ptit-2025-vong-luyen-tap-so-2-gdJzvbweJz5#_problem-j-9

You need to login in order to like this post: click here