Chọn ĐT Quốc gia ngày 2 năm học 2024- 2025 Thanh Hóa
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho dãy số gồm N số nguyên dương a1, a2, … aN. Một dãy con ai1, ai2, ai3, …, aik với i1 < i2 < i3 < … < ik được gọi là dãy con tăng khi ai1 < ai2 < ai3 < … < aik. Cho Q truy vấn, truy vấn thứ i (i=1..Q) được mô tả bởi hai số nguyên dương pi và xi. Với mỗi truy vấn, thay phần tử ở vị trí pi bằng xi. Lưu ý: việc thay đổi này chỉ có tác dụng với một truy vấn đó.
Yêu cầu: Tìm độ dài dãy con tăng dài nhất sau mỗi truy vấn.
Dữ liệu: Vào từ tệp văn bản LIS.INP gồm:
- Dòng đầu tiên chứa hai số nguyên dương N, Q (N, Q ≤ 3.10^5).
- Dòng thứ hai gồm N số nguyên dương a1, a2, …, aN (ai ≤ 10^9).
- Q dòng tiếp theo, mỗi dòng gồm hai số nguyên dương pi và xi (pi ≤ N, xi ≤ 10^9) mô tả một truy vấn.
Kết quả: Ghi ra tệp văn bản LIS.OUT gồm Q dòng, dòng thứ i in ra một số nguyên dương là câu trả lời cho truy vấn thứ i (i=1..Q).
Ví dụ:
LIS.INP LIS.OUT
7 3 5
1 5 3 1 2 4 6 3
2 2 4
7 3
4 100 5
Ràng buộc:
- Có 3 điểm có: N, Q ≤ 300;
- Có 3 điểm tiếp theo có: N, Q ≤ 3000;
- Có 1 điểm còn lại không có ràng buộc gì thêm.
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho 2 số nguyên dương N, Q và một tập A có thể chứa các số nguyên dương, ban đầu A không chứa số nào. Có 2 loại truy vấn như sau: - Loại 1: Cho một số nguyên dương x (x ≤ N), nếu x chưa có trong A thì thêm x vào A, ngược lại thì xóa x khỏi A. - Loại 2: Cho 2 số nguyên dương L, R (L ≤ R ≤ N), yêu cầu kiểm tra xem trong tập A có tồn tại 2 số x, y khác nhau nào mà L ≤ x, y ≤ R và ước số chung lớn nhất giữa x và y khác 1.
Yêu cầu: Thực hiện Q truy vấn, mỗi truy vấn là một trong hai loại trên.
Dữ liệu: Vào từ tệp văn bản NRS.INP gồm:
- Dòng đầu chứa hai số nguyên dương N, Q (N ≤ 10^6, Q ≤ 2.10^5);
- Q dòng tiếp theo, mỗi dòng chứa một truy vấn:
- Nếu là truy vấn loại 1 thì có dạng: S x với S là kí tự S và x là số cần thêm (hoặc xóa) khỏi A.
- Nếu là truy vấn loại 2 thì có dạng: C L R với C là kí tự C và L, R là 2 số nguyên dương như mô tả phía trên.
Kết quả: Ghi ra tệp NRS.OUT với mỗi truy vấn loại 2 trên một dòng, ghi YES nếu tồn tại hai số x, y như mô tả, ngược lại thì ghi NO.
Ví dụ:
NRS.INP NRS.OUT
11 6 YES
S 4 NO
S 10 YES
C 3 11
C 2 7
S 6
C 2 7
Ràng buộc:
- Có 1.5 điểm có N ≤ 100, Q ≤ 200;
- Có 1.5 điểm tiếp theo có L = 1, R = N với mọi truy vấn loại 2;
- Có 4 điểm còn lại không có ràng buộc gì thêm.
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Tôm có một cái đèn chùm gồm có N bóng đèn nhỏ đánh số từ 1 đến N, các bóng đèn nhỏ được nối với nhau bởi N-1 dây dẫn, mỗi dây dẫn sẽ nối trực tiếp hai bóng đèn nhỏ. Các dây được thiết kế sao cho giữa hai bóng đèn nhỏ bất kì đều được nối với nhau thông qua một số dây dẫn trực tiếp hoặc gián tiếp. Ở mỗi bóng đèn nhỏ có một công tắc bật (tắt), nếu bấm vào công tắc thì đèn đó đang sáng sẽ tắt và ngược lại đang tắt sẽ sáng. Ban đầu, có một số (lớn hơn 0) bóng đèn nhỏ ở trạng thái tắt. Tôm cần chọn ra một dãy các bóng đèn nhỏ sao cho giữa hai bóng đèn liên tiếp được chọn sẽ có dây dẫn trực tiếp, lưu ý trong dãy bóng này, các bóng đèn có thể lặp lại. Sau đó, Tôm lần lượt đi qua hết các bóng đèn theo thứ tự đã chọn, đi tới đâu Tôm sẽ bấm công tắc một lần ở bóng đèn đó, kết thúc một lượt bấm công tắc như vậy thì tất cả N bóng đèn nhỏ sẽ ở trạng thái bật sáng.
Yêu cầu: Chọn dãy bóng đèn nhỏ như mô tả trên sao cho dãy đó có độ dài ngắn nhất.
Dữ liệu: Vào từ tệp văn bản DENCHUM.INP theo khuôn dạng:
- Dòng đầu ghi số nguyên dương N (N ≤ 100);
- Dòng thứ hai chứa một xâu kí tự độ dài N, chỉ gồm các kí tự '0' hoặc '1'. Kí tự thứ i bằng '1' tức là bóng đèn thứ i ban đầu đang sáng, ngược lại bằng '0' tức là bóng đèn thứ i ban đầu tắt (với mọi i = 1..N).
- Mỗi dòng trong N-1 dòng tiếp theo ghi 2 số u, v (1 ≤ u, v ≤ N) mô tả có một dây dẫn trực tiếp giữa u và v.
Kết quả: Ghi ra tệp văn bản DENCHUM.OUT một số nguyên duy nhất là độ dài của dãy bóng đèn tìm được theo yêu cầu. Dữ liệu đảm bảo luôn tồn tại đáp án.
Ví dụ:
DENCHUM.INP
5
00100
1 2
2 3
2 4
3 5
DENCHUM.OUT
8
Giải thích ví dụ
Dãy bóng đèn có độ dài bằng 8 tìm được là:
1 2 4 2 3 5 3 2
Ràng buộc:
- Có 3 điểm có N ≤ 20.
- Có 3 điểm còn lại không có ràng buộc gì thêm.