Tổng quan đề thi
| Tên bài | Tên file chương trình | Tên file dữ liệu vào | Tên file dữ liệu ra | Điểm | |
| Bài 1 | Chuỗi may mắn | SLUCKY.* | SLUCKY.INP | SLUCKY.OUT | 7 |
| Bài 2 | Phòng dịch | GCDTREE.* | GCDTREE.INP | GCDTREE.OUT | 7 |
| Bài 3 | Hệ thống đèn | LISYS.* | LISYS.INP | LISYS.OUT | 6 |
Lưu ý:
- Dấu * trong phần tên chương trình tương ứng với ngôn ngữ lập trình mà thí sinh sử dụng, ví dụ PAS, CPP,….
Bài 1. Chuỗi may mắn
https://chuyentinpbc.ucode.vn/problems/gjw-nc1-slucky-178916
Số 6 và số 8 là những con số đẹp. Một xâu ký tự chỉ chứa ký tự '6' và ký tự '8' được gọi là một xâu ký tự may mắn. MK xác định "độ may mắn" của một xâu ký tự may mắn s như sau:
- Khởi đầu độ may mắn được gán là 0
- Xác định tập hợp P sao cho với mọi i ∈P thì s[i]='6' và s[i+1]='8' (ví dụ nếu s='866866868' thì P={3, 6, 8}). Lấy tổng tất cả các số trong P cộng thêm vào độ may mắn hiện có. Nếu P là tập rỗng thì quá trình tính độ may mắn dừng. Nếu không thực hiện tiếp bước 3
- Với i∈P xóa ký tự s[i] và s[i+1] khỏi dãy s (ví dụ sau khi xóa dãy s trong bước 1 trở thành s='866'). Sau đó lặp lại bước 2
Yêu cầu: Hãy tính độ may mắn của một xâu ký tự may mắn.
Dữ liệu vào:
- Dòng thứ nhất chứa số nguyên dương n≤105 là độ dài của một xâu ký tự may mắn
- Dòng thứ hai chứa một xâu ký tự may mắn độ dài n
Dữ liệu ra: Một số nguyên là độ may mắn của xâu ký tự tương ứng
Ví dụ:
| SLUCKY.INP | SLUCKY.OUT |
|---|---|
| 10 6668688868 | 20 |
Giải thích: Có ba lần xóa. Lần xóa đầu tiên P={3,5,9}. Ở lần xóa thứ hai s=6688, P={2}. Ở lần xóa thứ ba s=68, P={1}. Câu trả lời là 3+5+9+2+1=20
Ràng buộc:
- Có 50% số test ứng với n ≤2000
- Có 50% số test còn lại không có ràng buộc gì thêm.
Bài 2. Phòng dịch
https://chuyentinpbc.ucode.vn/problems/gjw-nc2-gcdtree-178917
Đại dịch Covid-19 bùng phát dẫn đến phải giãn cách xã hội khiến nhiều khu dân cư bị phong tỏa. Và lần này, Chính phủ cần bạn hỗ trợ trong việc tính toán sự tách biệt của một khu dân cư. Khu dân cư bạn sắp tính toán có n hộ dân, hộ dân thứ i có chỉ số cần trợ giúp là ai. Biết rằng có n-1 con đường nối giữa 2 hộ dân và từ mỗi hộ dân có thể đến mọi hộ dân khác qua các con đường. Đồng thời giữa 2 hộ dân chỉ có duy nhất một cách đi. Một cặp hộ dân thứ x và y (x được gọi là tách rời cấp độ i nếu (ước chung nhỏ nhất) của chỉ số cần trợ giúp các hộ dân trên đường đi giữa 2 hộ dân đó bằng chính xác i. Với mỗi i sao cho tồn tại ít nhất một cặp hộ dân có độ tách rời cấp độ i.
Yêu cầu: Hãy in ra i và số cặp hộ dân đang ở độ tách rời cấp i trên mỗi dòng với i tăng dần.
Dữ liệu vào: Vào từ file văn bản GCDTREE.INP có khuôn dạng sau:
- Dòng 1: chứa số nguyên n số các hộ dân.
- Dòng 2: dãy số nguyên dương là chỉ số cần trợ giúp của các hộ dân.
- n-1 dòng tiếp theo: mỗi dòng chứa 2 số nguyên dương x, y là cặp hộ dân.
Dữ liệu ra: Ghi ra file văn bản LISYS.OUT
In ra i và số cặp hộ dân đang ở độ tách rời cấp i trên mỗi dòng với i tăng dần
Ví dụ:
| GCDTREE.INP | GCDTREE.OUT |
|---|---|
| 3 1 2 3 1 2 2 3 | 1 3 |
| 8 3 5 3 5 3 6 3 2 1 8 8 2 2 3 1 4 8 6 3 7 3 5 | 1 24 2 1 3 3 |
Ràng buộc:
- Có 40% số test ứng với: n< 1000
- Có 30% số test ứng với: n, ai<5000
- Có 30% số test ứng với: 1<n, ai< 105
Bài 3. Hệ thống đèn
https://chuyentinpbc.ucode.vn/problems/gjw-nc1-lysys-178918
Một hệ thống đèn gồm 𝑚 × 𝑛 đèn, được bố trí trên một lưới hình chữ nhật gồm 𝑚 hàng và 𝑛 cột. Các hàng của lưới được đánh số từ 1 đến 𝑚 từ trên xuống dưới, các cột của lưới được đánh số từ 1 đến 𝑛 từ trái sang phải. Ô nằm giao giữa hàng 𝑖 (𝑖 = 1, 2, … , 𝑚) và cột 𝑗 (𝑗 = 1, 2, … , 𝑛) được gọi là ô (𝑖, 𝑗). Mỗi ô chứa đúng một đèn, mỗi đèn có 3 trạng thái, trạng thái sáng màu xanh hoặc sáng màu đỏ hoặc tắt. Có 𝑚 nút bấm điều khiển 𝑚 hàng, nút bấm điều khiển hàng thứ 𝑖 (𝑖 = 1, 2, … , 𝑚) được đánh chỉ số là 𝑖. Có 𝑛 nút bấm điều khiển 𝑛 cột, nút bấm điều khiển cột thứ 𝑗 (𝑗 = 1, 2, … , 𝑛) được đánh chỉ số là 𝑚 + 𝑗. Khi một nút điều khiển được bấm, nếu nó là nút điều khiển hàng, nó sẽ thay đổi trạng thái tất cả các đèn trên hàng đó, còn nếu nó là nút điều khiển cột, nó sẽ thay đổi trạng thái tất cả các đèn trên cột đó. Cụ thể, nếu một đèn đang ở trạng thái tắt sẽ chuyển sang trạng thái sáng màu xanh, còn nếu đang ở trạng thái sáng màu xanh thì chuyển sang trạng thái sáng màu đỏ, nếu ở trạng thái sáng màu đỏ thì chuyển về trạng thái tắt.
Yêu cầu: Cho trạng thái ban đầu của 𝑚 × 𝑛 đèn và dãy gồm 𝑠 thao tác bấm nút điều khiển. Hãy cho biết, sau khi thực hiện xong dãy thao tác thì có bao nhiêu đèn ở trạng thái tắt.
Dữ liệu: Vào từ file văn bản LISYS.INP có khuôn dạng sau:
- Dòng đầu chứa ba số nguyên 𝑚, 𝑛, 𝑠.
- Dòng thứ 𝑖 trong 𝑚 dòng tiếp theo, mỗi dòng chứa 𝑛 số nguyên 𝑐(𝑖,1), 𝑐(𝑖,2), … , 𝑐(𝑖,𝑛), trong đó 𝑐(𝑖,𝑗) tương ứng bằng 0 hoặc 1 hoặc 2 nếu đèn ở ô (𝑖, 𝑗) tương ứng đang ở trạng thái tắt hoặc sáng màu xanh hoặc sáng màu đỏ (𝑖 = 1, 2, … , 𝑚; 𝑗 = 1, 2, … , 𝑛).
- Cuối cùng là một dòng chứa 𝑠 số nguyên 𝑡1, 𝑡2, … , 𝑡𝑠 mô tả dãy gồm 𝑠 thao tác bấm nút điều khiển (1 ≤ 𝑡𝑘≤ 𝑚 + 𝑛; 𝑘 = 1, 2, … , 𝑠).
Kết quả: Ghi ra file văn bản LISYS.OUT gồm một số nguyên là số lượng đèn tắt sau khi thực hiện xong dãy thao tác điều khiển.
Ràng buộc:
- Có 30% số lượng test thỏa mãn điều kiện: 𝑚, 𝑛 ≤ 20 và 𝑠 = 0;
- Có 30% số lượng test khác thỏa mãn điều kiện: 𝑚, 𝑛, 𝑠 ≤ 20;
- Có 20% số lượng test khác thỏa mãn điều kiện: 𝑚 ≤ 20; 𝑛 ≤ 50000 và 𝑠 ≤ 106;
- Có 20% số lượng test còn lại thỏa mãn điều kiện: 𝑚 ≤ 50000; 𝑛 ≤ 20 và 𝑠 ≤ 106.
Ví dụ:
| LISYS.INP | LISYS.OUT | | LISYS.INP | LISYS.OUT |
| 2 3 0 0 0 0 0 0 2 | 5 | 3 5 0 0 2 0 1 1 2 2 1 1 1 1 2 2 0 1 | 3 |
Giải thuật tham khảo:
Bài 1: Chuỗi may mắn
Với subtask 1 đơn giản chỉ cần sử dụng kiểu string của C++ với các phép xóa. Chú ý là khi xóa thì lặp từ cuối xâu về đầu xâu.
Với subtask 2:
Giả sử xâu đã cho có dạng … , . Khi đó với mỗi vị trí ta tính T[i] là lượt xóa mà trong lượt này ký tự bj xóa. Điều này có thể làm bằng cách sử dụng một ngăn xếp:
ST là ngăn xếp.
- xâu ký tự may mắn
FOR i: 1 -> length of S
IF (S* == '6')
ST.push(i)
ELSEIF (S* == '8' and ST is not empty):
- = st->top;
St.pop
- = I;
//U and V is a matched pair
- = T[V] = max(T*, U < i < V) (*)
ENDIF
ENDFOR
Nếu ký tự không bị xóa thì để giá trị T đủ lớn (=n)
Trong đoạn đánh dấu (*) ở trên ta cần tìm giá trị lớn nhất của một đoạn trong mảng T. Điều này có thể được thực hiện bằng cách sử dụng IT khi đó thời gian thực hiện là O(n logn) (nếu khéo hơn có thể dùng sttack - O(n)).
Sau khi đã có mảng T thì dễ thấy với vị trí nếu nó bị xóa (T[i]<n) thì điểm nó được cộng thêm vào kết quả là số lượng giá trị T từ 1 đến i có giá trị lớn hơn hoặc bằng T[i]. Ta có thể sử dụng một BIT tổng để làm điều này.
Bài 2: Phòng dịch
Ta xét cạnh giữa 2 đỉnh
và
, đặt cho nó trọng số là
. Vậy khi đó, nếu ta xét một đồ thị với toàn bộ các cạnh là bội của
, thì nó sẽ tạo thành một rừng cây con. Và số cặp đường đi của đồ thị sẽ chính bằng tổng số cặp đường đi ở các cây con, và bằng số cặp có thể chọn ở các cây con. Đó chính là giá trị
ta cần tìm. Vậy với từng
, ta sẽ dựng một đồ thị với các cạnh có trọng số là bội của
đã được lưu từ trước. Để ý nếu ta DFS thử tất cả các điểm như ta thường làm, độ phức tạp của mỗi lần sẽ lên tới
và hoàn toàn vượt quá giới hạn. Do đó, ta sẽ chỉ DFS từ từng đầu mút của cạnh một trong các cạnh đã cho. Ta để ý số có nhiều ước số nhất trong khoảng
có 128 ước số, vậy mỗi cạnh sẽ xuất hiện trong tối đa 128 thao tác dựng đồ thị, và đảm bảo thời gian chạy cho chúng ta ở mức an toàn.
Bài 3: Hệ thống đèn
Gọi a[i] là số lần tác động lên những bóng đèn ở hàng dọc thứ i;
Gọi b[i] là số lần tác động lên những bóng đèn ở hàng ngang thứ i;
Với mỗi lần tác động , ta cập nhập giá trị mảng a ( hay b ) ;
Duyệt tất cả các bóng đèn , với mỗi bóng đèn , gọi p[i][j] là trạng thái ban đầu của bóng đèn hàng I cột j , a[j] + b[i] số lần tác động thêm vào bóng đèn hàng I cột j , nếu p[i][j] + a[j] + b[i] chia hết cho 3 thì tức là bóng đèn đó đang ở trạng thái tắt , khi đó kết quả cộng lên 1 ;
Độ phức tạp O ( m*n + q )



Bình luận