Cho một dãy số gồm N phần tử A1, A2, …, AN. Kujoh muốn biết dãy liên tiếp dài nhất chỉ…
- User
Cho một dãy số gồm N phần tử A1, A2, …, AN. Kujoh muốn biết dãy liên tiếp dài nhất chỉ gồm phần tử có duy nhất giá trị lẻ hoặc duy nhất giá trị chẵn có độ dài là bao nhiêu. Các bạn hãy giúp Kujoh nhé. Dữ liệu: Vào từ file văn bản BAI2.INP gồm:
- Dòng đầu tiên gồm số nguyên dương N là số lượng phần tử của dãy.
- Dòng thứ hai gồm các phần tử A1, A2, …, AN, mỗi phần tử cách nhau bởi một dấu cách (|Ai| ≤ 109). Kết quả: Ghi ra file BAI2.OUT là kết quả của đề bài. Ví dụ: BAI2.INP BAI2.OUT 10 1 2 13 1 5 2 2 0 0 3 4 Subtask 1: N ≤ 20. (60% số điểm) Subtask 2: N ≤ 106. (40% số điểm) Viết chương trình bằng C++
- Assistant
Để giải bài toán này, chúng ta cần tìm đoạn liên tiếp dài nhất trong dãy chỉ chứa các số chẵn hoặc chỉ chứa các số lẻ. Chúng ta sẽ sử dụng chiến lược duyệt qua dãy chỉ một lần (visual "two pointer" hoặc "sliding window" technique). Với mỗi phần tử, chúng ta theo dõi hai biến chiều dài lớn nhất cho toàn bộ dãy và cả hai đoạn liên tiếp hiện tại: một cho các số chẵn và một cho các số lẻ.
Dưới đây là mã nguồn C++ để giải bài toán này:
#include <iostream> #include <fstream> #include <vector> using namespace std; int main() { ifstream infile("BAI2.INP"); ofstream outfile("BAI2.OUT"); int N; infile >> N; vector<int> A(N); for (int i = 0; i < N; ++i) { infile >> A[i]; } int maxLength = 0; // độ dài dãy liên tiếp dài nhất int currentEvenLength = 0; // chiều dài hiện tại của dãy số chẵn liên tiếp int currentOddLength = 0; // chiều dài hiện tại của dãy số lẻ liên tiếp for (int i = 0; i < N; ++i) { if (A[i] % 2 == 0) { // nếu A[i] là số chẵn currentEvenLength++; currentOddLength = 0; // reset nếu gặp số lẻ } else { // nếu A[i] là số lẻ currentOddLength++; currentEvenLength = 0; // reset nếu gặp số chẵn } // Cập nhật độ dài lớn nhất maxLength = max(maxLength, max(currentEvenLength, currentOddLength)); } outfile << maxLength; infile.close(); outfile.close(); return 0; }Giải thích thuật toán:
- Đọc dữ liệu: Chương trình đọc giá trị
N(số phần tử) và mảngAtừ fileBAI2.INP. - Khởi tạo biến:
maxLengthđể lưu độ dài dãy liên tiếp dài nhất mà chỉ gồm số chẵn hoặc chỉ gồm số lẻ. Khởi tạo hai biếncurrentEvenLengthvàcurrentOddLengthđể lưu độ dài hiện tại của dãy liên tiếp số chẵn và dãy liên tiếp số lẻ tương ứng. - Duyệt qua mảng:
- Với mỗi phần tử, kiểm tra tính chẵn lẻ.
- Tăng độ dài của đoạn liên tiếp tương ứng.
- Đặt độ dài đoạn bên kia về 0.
- Cập nhật
maxLengthnếu tìm thấy đoạn dài hơn.
- Ghi kết quả: Kết quả được ghi vào file
BAI2.OUT.
Thuật toán này chạy trong O(N), đảm bảo hiệu quả với điều kiện tới 1 triệu phần tử trong dãy.
- Đọc dữ liệu: Chương trình đọc giá trị
- User
Nhà Kujoh có cầu thang với N bậc. Bậc thứ i cao hơn bậc thứ i-1 Ai mét. Bậc đầu tiên cao hơn mặt đất A1 mét, và mặt đất ở độ cao 0. Kujoh có Q câu hỏi k1, k2, …, kQ. Với mỗi câu hỏi ki, các bạn hãy tìm độ cao lớn nhất Kujoh có thể đến bằng cách leo cầu thang từ bậc 0 nếu chân bạn ấy dài ki mét. Kujoh có thể leo bậc thứ j nếu chân bạn ấy dài ít nhất Aj mét. Dữ liệu: Vào từ file văn bản BAI3.INP gồm:
- Dòng đầu tiên gồm 2 số nguyên dương N và Q.
- Dòng thứ hai gồm N số nguyên dương A1, A2, …, AN, mỗi số cách nhau bởi một dấu cách (Ai ≤ 109).
- Dòng thứ ba gồm Q số nguyên k1, k2, …, kQ. (0 ≤ ki ≤ 109). Kết quả: Ghi ra file BAI3.OUT gồm Q dòng, dòng thứ i là kết quả của câu hỏi thứ i. Ví dụ: BAI3.INP BAI3.OUT 4 5 1 2 1 5 1 2 4 9 10 1 4 4 9 9 Subtask 1: N ≤ 1000, Q ≤ 1000. (60% số điểm) Subtask 2: N, Q ≤ 2.10mũ 5 (40% số điểm) Viết chương trình bằng C++
- Assistant
Giải bài toán được mô tả, chúng ta sẽ cần tính toán khả năng của Kujoh để leo trên cầu thang với độ cao xác định theo tiêu chí mà chúng ta đưa ra. Cụ thể, chúng ta cần biết Kujoh có thể leo cao bao nhiêu bậc khi chân dài
kimét, dựa trên độ cao yêu cầu của mỗi bậc thang.Ý tưởng giải bài toán:
-
Lập mảng độ cao tích lũy (
H): Tạo mảngHđể lưu độ cao tích lũy của từng bậc, vớiH[i]là tổng độ cao từ bậc 0 đến bậc i. -
Xử lý các câu hỏi: Với mỗi độ dài chân
ki, đối với danh sách Q câu hỏi, tìm bậc cao nhất có thể leo lên mà chưa vượt quá khả năng của chân.
Chúng ta có thể tận dụng tính chất của bài toán và dữ liệu đã sắp xếp (tăng dần theo chiều từ bậc thấp đến bậc cao) để sử dụng tìm kiếm nhị phân nhằm tối ưu hóa việc tra cứu mỗi câu hỏi.
Dưới đây là mã C++ hoàn chỉnh cho bài toán:
#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; int main() { ifstream infile("BAI3.INP"); ofstream outfile("BAI3.OUT"); int N, Q; infile >> N >> Q; vector<int> A(N); for (int i = 0; i < N; ++i) { infile >> A[i]; } vector<int> k(Q); for (int i = 0; i < Q; ++i) { infile >> k[i]; } // Tính mảng độ cao tích lũy vector<long long> H(N + 1, 0); // H[0] = 0 for (int i = 1; i <= N; ++i) { H[i] = H[i - 1] + A[i - 1]; } // Xử lý từng câu hỏi for (int i = 0; i < Q; ++i) { int ki = k[i]; // Tìm kiếm nhị phân để tìm bậc cao nhất có thể leo với độ dài chân ki int low = 0, high = N, answer = 0; while (low <= high) { int mid = (low + high) / 2; if (A[mid] <= ki) { answer = mid + 1; // lưu trữ bậc này là có thể leo tới low = mid + 1; } else { high = mid - 1; } } // Lấy kết quả độ cao từ mảng tích lũy outfile << H[answer] << endl; } infile.close(); outfile.close(); return 0; }Giải thích chi tiết:
-
Mảng tích lũy
H:H[i]là tổng chiều cao từ bậc 0 đến bậc i, giúp dễ dàng xác định độ cao tới bậc i. -
Tìm kiếm nhị phân:
- Duyệt qua từng độ dài chân
kitrong danh sách các câu hỏi. - Với mỗi
ki, thực hiện tìm kiếm nhị phân trên mảngAđể tìm bậc cao nhất có thể leo tới (A[mid] <= ki).
- Duyệt qua từng độ dài chân
-
Quyết định kết quả: Sau khi xác định bậc cao nhất có thể leo, sử dụng mảng
Hđể xác nhận độ cao tích lũy cho câu trả lời tương ứng.
Với hướng đi này, chúng ta đảm bảo rằng thời gian xử lý vẫn nhanh chóng cho cả hai giá trị
NvàQlớn lên đến2*10^5, nhờ việc tối ưu hóa tìm kiếm với thuật toán tìm kiếm nhị phân. -
- User
Nhà Kujoh có cầu thang với N bậc. Bậc thứ i cao hơn bậc thứ i-1 Ai mét. Bậc đầu tiên cao hơn mặt đất A1 mét, và mặt đất ở độ cao 0. Kujoh có Q câu hỏi k1, k2, …, kQ. Với mỗi câu hỏi ki, các bạn hãy tìm độ cao lớn nhất Kujoh có thể đến bằng cách leo cầu thang từ bậc 0 nếu chân bạn ấy dài ki mét. Kujoh có thể leo bậc thứ j nếu chân bạn ấy dài ít nhất Aj mét. Dữ liệu: Vào từ file văn bản BAI3.INP gồm:
- Dòng đầu tiên gồm 2 số nguyên dương N và Q.
- Dòng thứ hai gồm N số nguyên dương A1, A2, …, AN, mỗi số cách nhau bởi một dấu cách (Ai ≤ 109).
- Dòng thứ ba gồm Q số nguyên k1, k2, …, kQ. (0 ≤ ki ≤ 109). Kết quả: Ghi ra file BAI3.OUT gồm Q dòng, dòng thứ i là kết quả của câu hỏi thứ i. 4 5 1 2 1 5 1 2 4 9 10 kết quả 1 4 4 9 9 Viết bài toán bằng C++
- Assistant
Để giải quyết bài toán này, chúng ta cần xác định khả năng leo cầu thang của Kujoh đối với mỗi câu hỏi
ki. Mục tiêu là tìm độ cao lớn nhất có thể đạt được mà bậc liên tiếp không cao hơn khả năng bước chân của Kujoh.Cách tiếp cận:
-
Tính toán độ cao tích lũy: Tạo một mảng để lưu tổng độ cao tại mỗi bậc. Điều này giúp chúng ta nhanh chóng biết được độ cao tổng cộng từ bậc đầu đến bậc i.
-
Duyệt qua mỗi câu hỏi
ki: Sử dụng tìm kiếm nhị phân để xác định bậc cuối cùng mà Kujoh có thể đạt được với khả năng bước chânki.
Dưới đây là mã C++ chi tiết cho bài toán:
#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; int main() { ifstream infile("BAI3.INP"); ofstream outfile("BAI3.OUT"); int N, Q; infile >> N >> Q; vector<int> A(N); for (int i = 0; i < N; ++i) { infile >> A[i]; } vector<int> k(Q); for (int i = 0; i < Q; ++i) { infile >> k[i]; } // Tính mảng độ cao tích lũy vector<long long> H(N + 1, 0); // H[i] là tổng độ cao đến bậc i for (int i = 1; i <= N; ++i) { H[i] = H[i - 1] + A[i - 1]; } // Xử lý từng câu hỏi for (int i = 0; i < Q; ++i) { int ki = k[i]; // Tìm kiếm nhị phân xác định bậc tối đa Kujoh có thể lên với bước chân ki int low = 0, high = N, answer = 0; while (low <= high) { int mid = (low + high) / 2; if (A[mid] <= ki) { answer = mid + 1; // Index bậc này có thể leo tới low = mid + 1; } else { high = mid - 1; } } // Lấy kết quả độ cao từ mảng tích lũy outfile << H[answer] << endl; } infile.close(); outfile.close(); return 0; }Giải thích chi tiết:
-
Mảng tích lũy
H: Tại mỗii,H[i]lưu độ cao tổng từ mặt đất đến bậci. -
Tìm kiếm nhị phân:
- Đối với mỗi
ki, thực hiện tìm kiếm nhị phân trên mảngAđể tìm bậc cuối cùng có thể với theo điều kiệnA[j] <= ki. - Sau khi xác định bậc tối đa có thể leo tới, sử dụng
Hđể xác định độ cao.
- Đối với mỗi
Với giải pháp này, ta tối ưu hóa việc xử lý cho cả hai điều kiện
N, Q ≤ 200,000, nhờ đó đảm bảo chương trình hoạt động nhanh chóng và hiệu quả. -