Có 2 loại gương như sau:
Tạm thời thế, input mình chưa update.
Trong 1 mê cung chứa những cái gương, một thằng trẻ con đứng tại ô 1,1 chiếu tia sáng theo phương từ trái qua phải, hỏi đến khi tia sáng ra khỏi mê cũng nó đã đi qua bao nhiêu cái gương. Có 2 loại gương như sau: 2 gương sẽ được cho trong ma trận NxM với giá trị tương ứng 1 và 2, như hình trên trước khi thoát ra khỏi mê cung thì tia sáng đã gặp 3 gương.
Tạm thời thế, input mình chưa update. Thật ra đề bài nó sẽ ra kiểu khác nhưng mình cứ nói yêu cầu đề cho các bạn dễ hiểu, mình có thể ghi đề chi tiết nhưng nếu thế sẽ không được cho phép (đại loại là k được tiết lộ đề thi). Nên mình sẽ mã hóa đề đi chút :D Trên bàn cờ vây chứa những quân cờ trắng và cờ đen. Bàn cờ vây được biểu thị dưới 1 ma trận kích thước NxN với giá trị 0 là quân trắng 1 là quân đen. Hãy đếm số cụm chứa quân đen và chỉ ra số lượng quân đen lớn nhất trong những cụm đó. Sample Input
Giải Thuật:
Dùng DFS hoặc BFS để đánh dấu những cụm đã check, trong quá trình đánh dấu thì đếm số lượng phần tử 1 của cụm. Download Solution Đề bài này hơi khó hiểu chút, cho một mạng gồm n router, tính khoảng thời gian time out để gửi lại gói tin khi xảy ra lỗi. Khoảng thời gian này là khoảng thời gian tối thiểu khi chọn 1 router trong mạng làm router trung tâm mà gói tin vẫn có thể đến tất cả các router còn lại. Giải thích : Test 2: Chọn 2 làm router trung tâm thì khoảng thời gian cần thiết sẽ là 1.
Test 3 : Chọn 1 làm router trung tâm khoảng thời gian cần thiết là 2. Giải thuật : Hãy liên tưởng đến bài toán tìm đường dài nhất trong đồ thị thì bài toán này sẽ là tìm số lượng điểm nhiều nhất giữa 2 router bất kì. Vẫn DFS 2 lần, lần 1 tại điểm bất kì và lần 2 tại điểm dài nhất đã tìm được ở lần 1. Thời gian cần thiết sẽ là tổng số node lớn nhất giữa 2 node + 1 chia 2. Trong một thí nghiệm giao phối giữa loài bọ, người ta đánh số chúng và cho chúng giao phối với nhau. Hãy kiểm tra xem có tồn tại con đồng tính trong những con được kiểm tra hay không? Code Editor
Bài này yêu cầu kiểm tra cây cho bởi input có phải là cây hay không. 1 đồ thị là cây khi có số đỉnh bằng số cạnh cộng thêm một, liên thông và không có chu trình. Solution
Cho n thị trấn và cho khoảng cách giữa 2 thị trấn. Hãy tìm ra con đường dài nhất giữa 2 thị trấn. Code Editor
Con đường dài nhất là 3 - 2 - 6 - 4 tương ứng với khoảng cách là 4 + 2 + 6 = 12
Giải thuật : DFS từ một thị trấn bất kì để tìm ra thị trấn xa nhất, sau đó DFS tại thị trấn xa nhất để tìm ra con đường dài nhất. Chú ý : Bài này input lớn nên các bạn có thể dùng vector để lưu trữ, yên tâm đề advanced của ss không bao giờ bắt cái linklist.
Cho một mảng danh sách chiều cao và số lượng người có chiều cao lớn hơn. Hãy tìm ra vị trí chính xác của mỗi người
Người có chiều cao 33 không có ai cao hơn đứng trước, người 11 có 2 người cao hơn đứng trước ...
Giải thuật: Sắp xếp lại mảng, điền dần vị trí của người có chiều cao thấp nhất đến người có chiều cao cao nhất. Sau khi sắp xếp ta được mảng chiều cao a[1, n] với người có chiều cao a[i] sẽ có x người đứng trước. x chính là số vị trí trống phía trước khi xếp người a[i] Sau khi sắp xếp ta có mảng sau. 11 22 33 44 55 tương ứng có dãy số người đứng trước như sau 2 1 0 1 0 điền 11 sao cho có 2 ô trống phía trước do đó 11 sẽ ở ô a[2], 22 có 11 người đứng trước sẽ ở ô a[1], và 33 ở ô a[0], sau đó 44 sẽ ở ô a[5] để đảm bảo trước nó có 1 ô trống.
Bài này yêu cầu tính chiều dài dãy kí tự tối đa có thể khi sử dụng n phím trên bàn phím.
Giải thuật: Dùng 1 mảng tần suất đánh đấu sự xuất hiện của các kí tự , dùng 1 cửa sổ trượt để duyệt chuỗi, khi cửa sổ này dùng hết n kí tự thì bắt đầu cập nhật leng của cửa sổ. Để tiếp tục thì ta xóa kí tự đầu tiên của cửa sổ này và tiếp tục duyệt để tìm chiều dài tối đa. |
Thời Gian
December 2021
Chủ ĐỀ
All
|