Tóm tắt đề bài

Cho dãy số nguyên \(A\) gồm \(n\) phần tử \(A_1, A_2, \dots, A_n\) và hai số nguyên \(U, V\). Hãy tìm một đoạn con liên tiếp \(A[i \dots j]\) có độ dài \(D\) thỏa mãn \(U \le D \le V\) sao cho tổng các phần tử trong đoạn con đó là lớn nhất.

Phân tích

• Điều kiện: \(1 \le U \le V \le n \le 10^5\), \(|A_i| \le 10^9\).
• Nhận xét:
  • Gọi \(P_i\) là tổng tiền tố của dãy số: \(P_i = A_1 + A_2 + \dots + A_i\) (với \(P_0 = 0\)).
  • Tổng của đoạn con từ vị trí \(i\) đến \(j\) (\(1 \le i \le j \le n\)) được tính bằng công thức: \(S(i, j) = P_j - P_{i-1}\).
  • Độ dài của đoạn con này là \(D = j - i + 1\).
  • Theo đề bài, ta cần tìm \(\max(P_j - P_{i-1})\) với điều kiện \(U \le j - i + 1 \le V\).
  • Đặt \(k = i - 1\), điều kiện trở thành \(U \le j - k \le V \Leftrightarrow j - V \le k \le j - U\).
  • Như vậy, với mỗi vị trí kết thúc \(j\) cố định, ta cần tìm vị trí \(k\) trong khoảng \([j-V, j-U]\) sao cho \(P_k\) là nhỏ nhất để hiệu \(P_j - P_k\) đạt cực đại.

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

Ý tưởng

Duyệt qua tất cả các cặp \((i, j)\) có thể có của đoạn con, kiểm tra xem độ dài có nằm trong khoảng \([U, V]\) hay không. Nếu thỏa mãn, tính tổng và cập nhật kết quả lớn nhất.

Độ phức tạp

• Thời gian: \(O(n^2)\)
• Đánh giá: Với \(n = 10^5\), cách này sẽ bị quá thời gian (TLE). Cách này chỉ phù hợp với \(n \le 5000\).

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

Nhận xét

Bài toán đưa về việc tìm giá trị nhỏ nhất của \(P_k\) trong một cửa sổ trượt có độ dài thay đổi. Cụ thể, với mỗi \(j\) chạy từ \(U\) đến \(n\), ta tìm:

Thuật toán

1. Xây dựng mảng tổng tiền tố \(P\).
2. Sử dụng một Deque để lưu trữ các chỉ số \(k\) sao cho \(P_k\) tăng dần.
3. Duyệt \(j\) từ \(U\) đến \(n\):
   • Khi \(j\) tăng lên, ứng viên mới cho vị trí \(k\) là \(k = j - U\). Ta thêm \(P_{j-U}\) vào Deque.
   • Trước khi thêm, loại bỏ các chỉ số \(idx\) ở cuối Deque mà \(P_{idx} \ge P_{j-U}\) vì chúng không còn khả năng làm giá trị nhỏ nhất.
   • Loại bỏ chỉ số ở đầu Deque nếu nó nằm ngoài phạm vi cho phép (nhỏ hơn \(j - V\)).
   • Giá trị \(P_k\) nhỏ nhất hiện tại chính là \(P_{dq.front()}\).
   • Cập nhật \(ans = \max(ans, P_j - P_{dq.front()})\).

Độ phức tạp

• Thời gian: \(O(n)\), mỗi phần tử được thêm vào và lấy ra khỏi Deque tối đa một lần.
• Bộ nhớ: \(O(n)\) để lưu mảng tổng tiền tố và Deque.

Tóm tắt đề bài

Cho \(n\) thiết bị âm thanh với giá thuê lần lượt là \(a_1, a_2, \dots, a_n\). Ta cần chia \(n\) thiết bị này thành các nhóm để thuê. Có hai chính sách tính tiền cho mỗi nhóm:
1. Nếu nhóm có từ \(3\) thiết bị trở lên: Miễn phí \(1\) thiết bị có giá nhỏ nhất trong nhóm đó.
2. Nếu nhóm có ít hơn \(3\) thiết bị: Tất cả thiết bị trong nhóm được giảm giá \(q\%\).

Tìm phương án chia nhóm sao cho tổng số tiền phải trả là ít nhất.

Phân tích

• Điều kiện: \(n \leq 10^6\), \(q < 100\), \(a_i \leq 10^6\) và \(a_i\) luôn chia hết cho \(100\).
• Nhận xét 1: Với chính sách 1 (nhóm \(\geq 3\) thiết bị), để tối ưu nhất, ta nên chia nhóm có đúng \(3\) thiết bị. Nếu một nhóm có \(4\) hoặc \(5\) thiết bị, ta có thể tách ra thành một nhóm \(3\) và các nhóm nhỏ hơn để tận dụng giảm giá \(q\%\) hoặc thêm thiết bị vào để đủ một nhóm \(3\) khác nhằm được miễn phí thêm. Cụ thể, nếu nhóm có \(k > 3\) phần tử, ta chỉ được miễn phí \(1\) phần tử rẻ nhất. Nếu tách thành các nhóm \(3\), ta có cơ hội được miễn phí nhiều phần tử hơn.
• Nhận xét 2: Với chính sách 2 (nhóm \(< 3\) thiết bị), mỗi thiết bị đều được giảm \(q\%\). Điều này tương đương với việc mỗi thiết bị trong nhóm này sẽ có giá là \(a_i \times (100 - q) / 100\).
• Nhận xét 3: Để tối ưu hóa việc miễn phí phần tử rẻ nhất trong nhóm \(3\), ta nên sắp xếp mảng \(a\) theo thứ tự giảm dần. Khi đó, nếu chọn \(3\) phần tử liên tiếp \(a_i, a_{i+1}, a_{i+2}\) vào một nhóm, phần tử được miễn phí sẽ là \(a_{i+2}\) (phần tử nhỏ nhất trong 3 số).

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

Ý tưởng

Sử dụng quy hoạch động. Gọi \(f(i)\) là chi phí nhỏ nhất để thuê \(i\) thiết bị đầu tiên (sau khi đã sắp xếp giảm dần).
Tại mỗi bước \(i\), ta có các lựa chọn:

• Thiết bị thứ \(i\) vào một nhóm riêng (giảm \(q\%\)): \(f(i) = f(i-1) + a_i \times (100-q)/100\).
• Thiết bị \(i-1, i\) vào một nhóm (giảm \(q\%\)): \(f(i) = f(i-2) + (a_{i-1} + a_i) \times (100-q)/100\).
• Thiết bị \(i-2, i-1, i\) vào một nhóm (miễn phí \(a_i\)): \(f(i) = f(i-3) + a_{i-2} + a_{i-1}\).

Thực tế, lựa chọn nhóm 1 thiết bị và nhóm 2 thiết bị theo chính sách 2 là như nhau (đều giảm \(q\%\) trên từng máy). Nên ta chỉ cần xét 2 trường hợp:

1. Thiết bị \(i\) được giảm \(q\%\).
2. Ba thiết bị \(i, i-1, i-2\) lập thành một nhóm để được miễn phí \(a_i\).

Độ phức tạp

• Thời gian: \(O(n \log n)\) do sắp xếp, phần quy hoạch động mất \(O(n)\).
• Đánh giá: Phù hợp với mọi \(n \leq 10^6\). Tuy nhiên, với \(n\) nhỏ (Subtask 1), ta có thể dùng quay lui để duyệt mọi cách chia nhóm.

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

Thuật toán

1. Sắp xếp mảng \(a\) theo thứ tự giảm dần \(a_1 \ge a_2 \ge \dots \ge a_n\).
2. Gọi \(f(i)\) là tổng chi phí nhỏ nhất để thuê \(i\) thiết bị đầu tiên.
3. Công thức truy hồi:
   • Phương án 1: Thiết bị thứ \(i\) được đưa vào nhóm dùng chính sách giảm giá \(q\%\).
     
     \[ f(i) = f(i-1) + a_i \times \frac{100 - q}{100} \]
   • Phương án 2: Thiết bị thứ \(i, i-1, i-2\) (với \(i \ge 3\)) lập thành một nhóm dùng chính sách miễn phí thiết bị rẻ nhất. Vì mảng đã sắp xếp giảm dần nên \(a_i\) là thiết bị rẻ nhất trong cụm 3 này.
     
     \[ f(i) = f(i-3) + a_{i-2} + a_{i-1} \]
4. Kết quả cuối cùng là \(f(n)\).

Tại sao sắp xếp giảm dần lại tối ưu?

Khi chọn nhóm 3 thiết bị để được miễn phí 1 cái, ta muốn cái được miễn phí (\(a_i\)) phải có giá trị lớn nhất có thể. Việc sắp xếp giảm dần và lấy cụm 3 liên tiếp giúp ta "ghép" các thiết bị đắt tiền lại với nhau, từ đó thiết bị rẻ nhất trong nhóm 3 đó vẫn mang giá trị cao, giúp số tiền được giảm là tối đa.

Độ phức tạp

• Thời gian: \(O(n \log n)\) cho việc sắp xếp và \(O(n)\) cho quy hoạch động.
• Bộ nhớ: \(O(n)\) để lưu mảng và bảng DP.

Tóm tắt đề bài

Cho một dãy gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\). Yêu cầu tìm độ dài của dãy con liên tiếp dài nhất sao cho tất cả các phần tử trong dãy con đó cùng chia hết cho một số nguyên \(d > 1\). Nếu không tìm được dãy nào, in ra \(0\).

Phân tích

• Điều kiện: Một dãy con liên tiếp \(a_i, a_{i+1}, \dots, a_j\) thỏa mãn yêu cầu khi và chỉ khi ước chung lớn nhất (ƯCLN) của tất cả các phần tử trong đoạn đó lớn hơn \(1\):
  
  \[ \gcd(a_i, a_{i+1}, \dots, a_j) > 1 \]
• Ràng buộc:
  • Tổng \(n\) qua các bộ test không quá \(10^6\).
  • Giá trị \(|a_i| \le 10^6\). Lưu ý rằng \(\gcd(x, y) = \gcd(|x|, |y|)\), nên ta có thể lấy giá trị tuyệt đối của các phần tử ngay từ đầu.
  • Nếu \(a_i = 0\), nó chia hết cho mọi số \(d\). Tuy nhiên, trong bài toán thực tế về mức chuẩn phục vụ, ta thường xét các số nguyên dương hoặc xử lý \(\gcd(0, x) = |x|\).

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ừ vị trí \(i\) đến \(j\). Với mỗi đoạn, ta tính \(\gcd\) của tất cả các phần tử. Nếu \(\gcd > 1\), ta cập nhật độ dài lớn nhất.

Độ phức tạp

• Thời gian: \(O(T \times n^2 \times \log(\max A))\)
• Đánh giá: Với \(n = 10^6\), cách này sẽ bị quá thời gian (TLE). Chỉ phù hợp với Subtask 1 (\(n \le 1000\)).

Code Brute Force

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

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] = abs(a[i]);
    }
    int max_len = 0;
    for (int i = 0; i < n; i++) {
        int current_gcd = 0;
        for (int j = i; j < n; j++) {
            current_gcd = gcd(current_gcd, a[j]);
            if (current_gcd > 1) {
                max_len = max(max_len, j - i + 1);
            } else {
                break;
            }
        }
    }
    cout << max_len << endl;
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

import math

def solve():
    try:
        line1 = input().split()
        if not line1: return
        n = int(line1[0])
        a = list(map(int, input().split()))
    except EOFError:
        return

    a = [abs(x) for x in a]
    max_len = 0
    for i in range(n):
        current_gcd = 0
        for j in range(i, n):
            current_gcd = math.gcd(current_gcd, a[j])
            if current_gcd > 1:
                max_len = max(max_len, j - i + 1)
            else:
                break
    print(max_len)

t_str = input()
if t_str:
    t = int(t_str)
    for _ in range(t):
        solve()

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

Nhận xét

1. Một dãy con có \(\gcd > 1\) khi và chỉ khi tất cả các phần tử trong dãy đó cùng chia hết cho ít nhất một số nguyên tố \(p\).
2. Thay vì duyệt mọi đoạn con, ta có thể duyệt qua từng số nguyên tố \(p\) và tìm đoạn con liên tiếp dài nhất mà mọi phần tử đều chia hết cho \(p\).
3. Các số nguyên tố cần xét chỉ nằm trong khoảng từ \(2\) đến \(\max|a_i| = 10^6\).

Thuật toán

1. Sử dụng sàng Eratosthenes để tiền xử lý: Với mỗi số \(x \in [2, 10^6]\), tìm các ước nguyên tố của nó. Để tối ưu, ta chỉ cần lưu ước nguyên tố nhỏ nhất min_prime[x].
2. Với mỗi số \(a_i\) trong mảng:
   • Phân tích \(a_i\) thành các thừa số nguyên tố khác nhau.
   • Với mỗi thừa số nguyên tố \(p\), ta biết \(a_i\) có thể đóng góp vào một dãy chia hết cho \(p\).
3. Sử dụng một mảng (hoặc map) pos[p] để lưu độ dài của dãy con liên tiếp chia hết cho \(p\) kết thúc tại vị trí hiện tại.
   • Khi xét đến \(a_i\), với mỗi ước nguyên tố \(p\) của \(a_i\):
     • Nếu \(a_{i-1}\) cũng chia hết cho \(p\), thì current_len[p] = current_len[p] + 1.
     • Nếu không, current_len[p] = 1.
   • Cập nhật kết quả cực đại từ current_len[p].
   • Lưu ý quan trọng: Để tránh việc reset mảng current_len cho mỗi bộ test (gây TLE), ta có thể dùng một mảng đánh dấu hoặc chỉ reset những vị trí đã sử dụng.

Độ phức tạp

• Tiền xử lý: \(O(M \log \log M)\) với \(M = 10^6\).
• Xử lý mỗi test: \(O(n \times \omega(a_i))\), trong đó \(\omega(a_i)\) là số lượng ước nguyên tố khác nhau của \(a_i\) (rất nhỏ, tối đa 7 vì \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 > 10^6\)).
• Tổng thời gian: \(O(M \log \log M + \sum n \cdot \omega(a_i))\), hoàn toàn đáp ứng thời gian 1-2s.

Tóm tắt đề bài

Có \(n\) khách hàng xếp hàng mua bánh. Khách hàng thứ \(i\) muốn mua \(a_i\) chiếc bánh và chỉ sẵn sàng chờ tối đa \(t_i\) phút. Thời gian phục vụ mỗi khách là \(1\) phút. Cửa hàng phục vụ theo đúng thứ tự xếp hàng nhưng có thể từ chối phục vụ bất kỳ ai. Một khách hàng được phục vụ nếu thời điểm bắt đầu phục vụ họ không quá \(t_i\). Tìm tổng số bánh lớn nhất có thể bán được.

Phân tích

• Điều kiện: \(n \le 10^4, t_i \le 10^4, a_i \le 10^5\).
• Nhận xét quan trọng:
  • Giả sử chúng ta chọn phục vụ một tập hợp các khách hàng. Để phục vụ được nhiều bánh nhất, ta cần sắp xếp họ theo đúng thứ tự ban đầu (vì đề bài yêu cầu phục vụ theo đúng thứ tự xếp hàng).
  • Nếu ta chọn phục vụ \(k\) khách hàng, khách hàng được chọn thứ \(j\) (\(1 \le j \le k\)) sẽ được phục vụ tại thời điểm \(j-1\). Do đó, điều kiện để khách hàng này không bỏ đi là \(j-1 \le t_i\), hay \(j \le t_i + 1\).
  • Điều này có nghĩa là: Nếu ta chọn một nhóm khách hàng, khách hàng thứ \(i\) trong danh sách ban đầu nếu được chọn và là người thứ \(j\) được phục vụ, thì \(j\) phải thỏa mãn \(j \le t_i + 1\).

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

Ý tưởng

Sử dụng quy hoạch động. Gọi \(dp[i][j]\) là số bánh lớn nhất bán được khi xét đến khách hàng thứ \(i\) và đã phục vụ được \(j\) khách hàng.

• Nếu không phục vụ khách thứ \(i\): \(dp[i][j] = dp[i-1][j]\)
• Nếu phục vụ khách thứ \(i\): Điều kiện là \(j-1 \le t_i\) (vì khách \(i\) là người thứ \(j\) được phục vụ, bắt đầu tại thời điểm \(j-1\)).
  • \(dp[i][j] = \max(dp[i][j], dp[i-1][j-1] + a_i)\)

Độ phức tạp

• Thời gian: \(O(n^2)\) do có 2 vòng lặp lồng nhau.
• Bộ nhớ: \(O(n^2)\) hoặc \(O(n)\) nếu tối ưu mảng một chiều.
• Đánh giá: Với \(n = 10^4\), \(O(n^2)\) rơi vào khoảng \(10^8\) phép tính, có thể kịp trong giới hạn thời gian nếu cài đặt tối ưu, nhưng có cách tiếp cận hiệu quả hơn bằng cấu trúc dữ liệu.

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

Nhận xét

Thay vì dùng quy hoạch động, ta có thể sử dụng chiến thuật tham lam kết hợp với hàng đợi ưu tiên (Priority Queue):

1. Duyệt qua từng khách hàng từ \(1\) đến \(n\).
2. Với mỗi khách hàng \(i\), ta tạm thời "giả định" sẽ phục vụ họ. Thêm \(a_i\) vào một hàng đợi ưu tiên (min-heap) và cộng \(a_i\) vào tổng số bánh.
3. Sau khi thêm khách hàng \(i\), số lượng khách hàng đang được chọn phục vụ là pq.size().
4. Nếu số lượng khách hàng vượt quá giới hạn chờ của khách hàng hiện tại (tức là pq.size() > t_i + 1), ta bắt buộc phải loại bỏ một khách hàng đã chọn trước đó để đảm bảo tính hợp lệ.
5. Để tổng số bánh là lớn nhất, ta sẽ loại bỏ khách hàng có số lượng bánh \(a_j\) nhỏ nhất trong số các khách đã chọn (đó là lý do dùng min-heap).

Tại sao cách này đúng?

Mặc dù đề bài yêu cầu phục vụ theo đúng thứ tự, nhưng điều kiện \(j \le t_i + 1\) chỉ phụ thuộc vào số lượng khách hàng được phục vụ trước khách hàng \(i\). Khi ta loại bỏ một khách hàng có \(a_j\) nhỏ nhất, ta giải phóng một "vị trí thời gian" cho các khách hàng phía sau mà không làm vi phạm điều kiện của các khách hàng đã chọn (vì việc loại bỏ chỉ làm giảm số thứ tự phục vụ của các khách đứng sau khách bị loại).

Độ phức tạp

• Thời gian: \(O(n \log n)\) do mỗi khách hàng được đẩy vào và lấy ra khỏi Priority Queue tối đa một lần.
• Bộ nhớ: \(O(n)\) để lưu trữ Priority Queue và dữ liệu khách hàng.