Ôn tập thi TS10 Chuyên tin 2026 -- Đề số 2

2025 TS10 (đề các tỉnh)

Bài 1

Tóm tắt đề bài

Cho số nguyên dương \(N\) là số lượng học sinh. Cần xếp \(N\) học sinh vào các hàng sao cho mỗi hàng có số lượng học sinh bằng nhau. Gọi \(R\) là số hàng và \(S\) là số học sinh mỗi hàng.
Điều kiện:

\(R \times S = N\)
\(R \le S\)

Yêu cầu: Tìm giá trị \(R\) lớn nhất thỏa mãn các điều kiện trên.

Phân tích

Điều kiện: \(1 \le N \le 10^{12}\).
- Vì \(R \times S = N\) nên \(R\) và \(S\) đều là các ước của \(N\).
- Từ điều kiện \(R \le S\), ta nhân cả hai vế với \(R\) (là số dương):
Nhận xét:

\[ R \times R \le R \times S \implies R^2 \le N \implies R \le \sqrt{N} \]
- Như vậy, bài toán quy về việc tìm ước lớn nhất của \(N\) mà không vượt quá \(\sqrt{N}\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt tất cả các số \(i\) từ 1 đến \(N\). Nếu \(i\) là ước của \(N\), ta tính số học sinh mỗi hàng tương ứng là \(j = N/i\). Nếu \(i \le j\), ta cập nhật kết quả là giá trị \(i\) lớn nhất tìm được.

Độ phức tạp

Thời gian: \(O(N)\)
Đánh giá: Chỉ phù hợp với Subtask 1 (\(N \le 10^6\)). Với \(N = 10^{12}\), cách này sẽ bị quá thời gian (TLE).

Hướng giải quyết (Tối ưu)

Nhận xét

Như đã phân tích ở trên, ta chỉ cần tìm các ước của \(N\) trong đoạn từ \(1\) đến \(\sqrt{N}\). Giá trị lớn nhất trong các ước này chính là số hàng tối đa có thể xếp được.

Thuật toán

Duyệt biến \(i\) từ 1 đến \(\sqrt{N}\) (điều kiện dừng là \(i \times i \le N\)).
Nếu \(N\) chia hết cho \(i\):
- \(i\) là một ứng cử viên cho số hàng (vì \(i \le \sqrt{N}\) nên chắc chắn \(i \le N/i\)).
- Cập nhật \(ans = \max(ans, i)\).
In ra \(ans\).

Độ phức tạp

Thời gian: \(O(\sqrt{N})\). Với \(N = 10^{12}\), \(\sqrt{N} = 10^6\), thuật toán chạy rất nhanh.
Bộ nhớ: \(O(1)\).

Bài 2

Tóm tắt đề bài

Cho một dãy gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) và một số nguyên \(k\). Một đoạn con liên tiếp được gọi là hợp lệ nếu số lượng giá trị phân biệt trong đoạn đó không vượt quá \(k\). Yêu cầu tìm độ dài lớn nhất của một đoạn con hợp lệ.

Phân tích

Điều kiện: \(1 \leq n, k \leq 10^5\), \(1 \leq a_i \leq 10^5\).
Nhận xét:
- Nếu một đoạn con từ vị trí \(l\) đến \(r\) hợp lệ, thì mọi đoạn con nằm bên trong nó (ví dụ từ \(l+1\) đến \(r\)) cũng chắc chắn hợp lệ vì số lượng giá trị phân biệt chỉ có thể giữ nguyên hoặc giảm đi.
- Khi ta cố định điểm kết thúc \(r\) và dịch chuyển \(r\) sang phải, điểm bắt đầu \(l\) tối ưu nhất (để đoạn dài nhất) cũng sẽ có xu hướng giữ nguyên hoặc dịch chuyển sang phải để giảm bớt số lượng giá trị phân biệt xuống mức \(\leq k\).
- Đây là tính chất đặc trưng để sử dụng kỹ thuật Cửa sổ trượt (Sliding Window) hoặc Hai con trỏ (Two Pointers).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua tất cả các cặp \((i, j)\) đại diện cho đoạn con từ \(i\) đến \(j\). Với mỗi đoạn, ta sử dụng một tập hợp (set trong C++ hoặc set() trong Python) để đếm số lượng phần tử phân biệt. Nếu số lượng này \(\leq k\), ta cập nhật độ dài lớn nhất.

Độ phức tạp

Thời gian: \(O(n^3)\) hoặc \(O(n^2 \log n)\) tùy vào cách cài đặt.
Đánh giá: Chỉ phù hợp cho Subtask 1 và 2 (\(n \leq 1000\)).

Hướng giải quyết (Tối ưu)

Thuật toán: Hai con trỏ (Two Pointers)

Ta sử dụng hai con trỏ \(l\) và \(r\) cùng xuất phát từ đầu dãy để đại diện cho đoạn \([l, r]\).

Sử dụng một mảng đếm (hoặc map) để lưu tần suất xuất hiện của các số trong đoạn hiện tại và một biến cur để đếm số lượng giá trị phân biệt.
Duyệt \(r\) từ \(1\) đến \(n\):
- Thêm \(a[r]\) vào đoạn: Nếu \(a[r]\) chưa có trong đoạn (tần suất bằng \(0\)), tăng cur.
- Tăng tần suất của \(a[r]\).
- Nếu cur > k: Ta phải thu hẹp đoạn bằng cách tăng \(l\). Mỗi khi tăng \(l\), giảm tần suất của \(a[l]\). Nếu tần suất của \(a[l]\) về \(0\), giảm cur. Lặp lại cho đến khi cur \leq k.
Sau mỗi bước dịch chuyển \(r\), độ dài đoạn hợp lệ hiện tại là \(r - l + 1\). Cập nhật kết quả cực đại.

Tại sao hiệu quả?

Mỗi con trỏ \(l\) và \(r\) chỉ chạy từ đầu đến cuối dãy đúng một lần, giúp giảm độ phức tạp từ \(O(n^2)\) xuống \(O(n)\).

Độ phức tạp

Thời gian: \(O(n)\) nếu dùng mảng đếm (do \(a_i \leq 10^5\)) hoặc \(O(n \log n)\) nếu dùng std::map.
Bộ nhớ: \(O(\max(a_i))\) để lưu mảng đếm hoặc \(O(n)\) để lưu map.

Bài 3

Tóm tắt đề bài

Cho \(n\) công việc, mỗi công việc \(i\) có thời gian thực hiện là \(T_i\) và hạn chót là \(D_i\). Ta bắt đầu làm việc từ ngày \(0\). Tại mỗi thời điểm chỉ làm được một công việc. Một công việc hoàn thành đúng hạn nếu thời điểm kết thúc của nó không vượt quá \(D_i\). Hãy tìm số lượng công việc tối đa có thể hoàn thành đúng hạn.

Phân tích

Điều kiện: \(n \le 10^5\), \(T_i, D_i \le 10^9\).
Nhận xét 1: Để tối ưu hóa việc chọn công việc, ta nên ưu tiên xem xét các công việc có hạn chót (\(D_i\)) sớm hơn trước. Đây là chiến lược tham lam phổ biến cho các bài toán lập lịch (scheduling).
Nhận xét 2: Giả sử ta đang xem xét công việc \(i\) theo thứ tự hạn chót tăng dần. Nếu việc thêm công việc \(i\) vào danh sách các công việc đã chọn làm tổng thời gian thực hiện vượt quá hạn chót \(D_i\), ta buộc phải loại bỏ một công việc nào đó trong danh sách đã chọn để "tiết kiệm" thời gian. Để số lượng công việc còn lại là nhiều nhất và dễ dàng chấp nhận các công việc sau này nhất, ta nên loại bỏ công việc có thời gian thực hiện (\(T_j\)) lớn nhất trong số các công việc đã chọn.

Cách làm đơn giản (Brute Force)

Ý tưởng

Với \(n \le 20\), ta có thể sử dụng quay lui (backtracking) hoặc duyệt nhị phân các tập con để thử tất cả các tổ hợp công việc. Với mỗi tập con, ta kiểm tra xem có tồn tại một thứ tự sắp xếp nào đó để tất cả công việc trong tập đó đều hoàn thành đúng hạn hay không (thứ tự tốt nhất luôn là sắp xếp theo \(D_i\) tăng dần).

Độ phức tạp

Thời gian: \(O(2^n \cdot n \log n)\)
Đánh giá: Chỉ phù hợp cho Subtask 1 (\(n \le 20\)).

Hướng giải quyết (Tối ưu)

Thuật toán

Sử dụng chiến lược tham lam kết hợp với cấu trúc dữ liệu Hàng đợi ưu tiên (Priority Queue):

Sắp xếp tất cả các công việc theo thứ tự hạn chót \(D_i\) tăng dần.
Duyệt qua từng công việc \(i\) sau khi đã sắp xếp:
- Thêm \(T_i\) vào tổng thời gian hiện tại (res).
- Đưa \(T_i\) vào một hàng đợi ưu tiên (max-heap) để quản lý thời gian của các công việc đã chọn.
- Nếu tổng thời gian res vượt quá hạn chót \(D_i\) của công việc hiện tại:
  - Ta phải loại bỏ một công việc đã chọn để giảm res. Công việc tối ưu nhất để loại bỏ là công việc có thời gian thực hiện \(T\) lớn nhất trong hàng đợi ưu tiên.
  - Lấy phần tử lớn nhất ra khỏi hàng đợi ưu tiên, trừ giá trị đó khỏi res.
Số lượng công việc còn lại trong hàng đợi ưu tiên chính là kết quả cần tìm.

Tại sao thuật toán này đúng?

Khi ta gặp một công việc \(i\) mà việc thêm nó vào làm tổng thời gian vượt quá \(D_i\), việc loại bỏ công việc có \(T\) lớn nhất sẽ giúp ta giảm thời gian tích lũy nhiều nhất có thể, từ đó tạo ra nhiều "khoảng trống" nhất cho các công việc có hạn chót xa hơn ở phía sau, mà không làm giảm số lượng công việc đã chọn (vì ta chỉ đổi 1 công việc lấy 1 công việc, hoặc bỏ bớt 1 nếu không thể đổi).

Độ phức tạp

Thời gian: \(O(n \log n)\) do thao tác sắp xếp và các thao tác trên Priority Queue.
Bộ nhớ: \(O(n)\) để lưu trữ danh sách công việc và hàng đợi ưu tiên.

```

Bài 4

Tóm tắt đề bài

Cho một xâu ký tự \(S\) độ dài \(N\) gồm các chữ cái in thường. Một xâu được gọi là "tiềm năng" nếu có thể sắp xếp lại các ký tự của nó để tạo thành một xâu đối xứng (palindrome). Nhiệm vụ của bạn là đếm số lượng đoạn con liên tiếp của \(S\) là xâu tiềm năng.

Phân tích

Đặc điểm của xâu tiềm năng: Một xâu có thể sắp xếp lại thành xâu đối xứng khi và chỉ khi có tối đa một loại ký tự xuất hiện lẻ lần.
- Nếu độ dài xâu chẵn: Tất cả các ký tự phải xuất hiện với số lần chẵn.
- Nếu độ dài xâu lẻ: Có đúng một ký tự xuất hiện lẻ lần, các ký tự còn lại xuất hiện chẵn lần.
Dạng bài toán: Đếm số đoạn con \([i, j]\) thỏa mãn điều kiện về tần suất ký tự. Với \(N = 10^5\), chúng ta cần một thuật toán có độ phức tạp khoảng \(O(N \times 26)\) hoặc \(O(N \log N)\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua tất cả các đoạn con \([i, j]\) của xâu \(S\). Với mỗi đoạn con, ta đếm số lần xuất hiện của từng ký tự từ a đến z. Nếu số lượng ký tự có tần suất lẻ không vượt quá \(1\), ta tăng biến đếm kết quả.

Độ phức tạp

Thời gian: \(O(N^2 \times 26)\) hoặc \(O(N^3)\) tùy cách cài đặt.
Đánh giá: Phù hợp cho Subtask 1 và 2 (\(N \leq 3000\)).

Hướng giải quyết (Tối ưu)

Nhận xét quan trọng

Vì chúng ta chỉ quan tâm đến việc một ký tự xuất hiện chẵn hay lẻ lần, ta có thể sử dụng Bitmask (mặt nạ bit) để biểu diễn trạng thái của xâu:

Một số nguyên mask có 26 bit. Bit thứ \(k\) bằng \(1\) nếu ký tự thứ \(k\) (từ a đến z) xuất hiện lẻ lần, và bằng \(0\) nếu xuất hiện chẵn lần.
Khi thêm một ký tự \(c\) vào xâu, ta cập nhật mask bằng phép toán XOR: mask ^= (1 << (c - 'a')).
Trạng thái của đoạn con từ \(i+1\) đến \(j\) có thể tính bằng: mask[j] ^ mask[i], trong đó mask[x] là trạng thái của tiền tố từ \(1\) đến \(x\).

Điều kiện để đoạn con \([i+1, j]\) là xâu tiềm năng:

mask[j] ^ mask[i] == 0: Tất cả ký tự xuất hiện chẵn lần (tổng cộng 0 bit 1).
mask[j] ^ mask[i] == (1 << k) với \(k \in [0, 25]\): Có đúng một ký tự xuất hiện lẻ lần (tổng cộng 1 bit 1).

Thuật toán

Sử dụng một bảng băm (hoặc mảng nếu giá trị mask nhỏ, nhưng ở đây mask lên tới \(2^{26}\) nên dùng unordered_map) để lưu số lần xuất hiện của các mask đã gặp.
Khởi tạo mask = 0 và freq[0] = 1 (biểu thị tiền tố rỗng).
Duyệt qua từng ký tự của xâu:
- Cập nhật mask hiện tại.
- Cộng vào kết quả số lượng mask cũ đã lưu trong map thỏa mãn mask ^ old_mask == 0 (tức là old_mask == mask).
- Với mỗi \(k\) từ \(0\) đến \(25\), cộng vào kết quả số lượng old_mask thỏa mãn mask ^ old_mask == (1 << k) (tức là old_mask == mask ^ (1 << k)).
- Tăng tần suất của mask hiện tại trong map.

Độ phức tạp

Thời gian: \(O(N \times 26)\) do duyệt xâu một lần và với mỗi vị trí kiểm tra 26 khả năng bit lẻ.

Bộ nhớ: \(O(N)\) để lưu trữ bảng băm.

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    if (!(cin >> s)) return 0;

    long long res = 0;
    // Sử dụng unordered_map để đếm số lần xuất hiện của mỗi mask
    unordered_map<int, int> freq;

    // Trạng thái ban đầu: xâu rỗng có mask = 0
    freq[0] = 1;
    int mask = 0;

    for (char c : s) {
        // Cập nhật mask cho ký tự hiện tại
        mask ^= (1 << (c - 'a'));

        // Trường hợp 1: Tất cả ký tự xuất hiện chẵn lần
        // mask ^ old_mask == 0  => old_mask == mask
        if (freq.count(mask)) {
            res += freq[mask];
        }

        // Trường hợp 2: Có đúng một ký tự xuất hiện lẻ lần
        // mask ^ old_mask == (1 << k) => old_mask == mask ^ (1 << k)
        for (int k = 0; k < 26; ++k) {
            int target = mask ^ (1 << k);
            if (freq.count(target)) {
                res += freq[target];
            }
        }

        // Lưu mask hiện tại vào map để dùng cho các bước sau
        freq[mask]++;
    }

    cout << res << endl;
    return 0;
}

Bình luận

Tải bình luận...

Không có bình luận nào.