NƯỚC ĐỌNG

Nguồn: http://vn.spoj.com/problems/V11WATER/

Năm 2011, tình trạng ngập lụt trong thành phố trở lên nghiêm trọng hơn. Vì vậy, mọi người quyết định xây dựng hệ thống mái che cho toàn thành phố.

Mái che có bề rộng là N, được chia làm N phần có độ dài như nhau. Độ cao của mỗi phần là h1, h2, ..., hn. Khi trời mưa, một phần nước sẽ đọng lại trên mái và một phần sẽ thoát ra ngoài theo hai bên trái và phải của mái che. Do đó, thành phố sẽ không phải chịu cảnh mưa lụt như trước.

Nhằm mục đích bảo trì mái che, bạn cần viết chương trình tính lượng nước lớn nhất có thể đọng lại trên mái che.

Dữ liệu vào: từ tệp V11WATER.INP

+ Dòng đầu ghi số N. (1 <= N <= 100000)

+ Dòng sau ghi N số tự nhiên h1, h2, ..., hn. (1 <= hi <= 100000)

Gồm một số duy nhất thể hiện lượng nước tìm được.

Dữ liệu ra: ghi vào tệp V11WATER.OUT

+ Môt số duy nhất thể hiện số lượng nước tìm được

Ví dụ:

V11WATER.INP	V11WATER.OUT
5 1 3 1 2 3	3

 SOLUTION - CODE

CÂY

Nguồn: http://vn.spoj.com/problems/VOTREE/

Cho cây gồm N đỉnh, có gốc ở đỉnh 1. (N ≤ 70,000). Bạn cần trả lời Q truy vấn, mỗi truy vấn gồm 2 số u, v. Bạn cần tìm đỉnh xa gốc nhất, mà là tổ tiên của tất cả các đỉnh u, u+1, ..., v.

Dữ liệu vào: VOTREE.INP

+ Dòng 1: Số nguyên dương N và Q.

+ N-1 dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương u và v, thể hiện có 1 cạnh nối giữa 2 đỉnh u và v. (u ≠ v, 1 ≤ u, v ≤ N).

 +Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương u và v (1 ≤ u ≤ v ≤ N), thể hiện 1 truy vấn.

Dữ liệu ra: Ghi vào tệp văn bản VOTREE.OUT

Với mỗi truy vấn, in ra 1 dòng duy nhất là đáp số của truy vấn.

Giới hạn:

+ Trong 30% số test, 1 ≤ N, Q ≤ 1000.

+ Trong tất cả các test, 1 ≤ N, Q ≤ 70,000.

+ Thời gian chạy: 1s. Thời gian chạy cho test ví dụ: 0.5s

Ví dụ:

VOTREE.INP	VOTREE.OUT
5 3 1 2 2 3 3 4 3 5 2 5 1 3 4 5	2 1 3

SOLUTION - CODE

Hướng dẫn tải file từ Blog

Hướng dẫn tải file từ Blog

Sau khi Click vào link nếu chuyển đến Dropbox thì các bạn tải về bình thường, nếu chuyển đến 1 trang Web rút gọn Link thì bạn xem ở dưới

Hoặc tải về ở đây: Word PDF

Sửa cầu

Nguồn: http://vn.spoj.com/problems/KBUILD/

Vì lo lắng Pirate sẽ buồn chán khi một thân một mình ở đảo hoang, bạn gái Pirate từ trong đất liền dự định sang chơi với anh ấy.

Pirate đang sinh sống trên một quần đảo gồm N đảo. Vì các đảo khá gần nhau nên chẳng cần thuyền bè gì, Pirate chỉ cần đốn đại cây dừa nào đó và bắc ngang là có thể đi được từ đảo này sang đảo khác. Vì không muốn hủy hoại môi trường nên anh ấy chỉ đốn N - 1 cây dừa làm cầu, vừa đủ để từ một đảo bất kì đi đến được hết mọi đảo còn lại.

Nhưng mà "Môi son, má đào, chân guốc cao gót làm sao em qua cầu dừa???". Lo lắng sợ bạn gái sẽ rơi xuống biển và bị cá đuối nẫng mất, Pirate hộc tốc đi sửa chữa các cây cầu dừa. Anh đưa ra một lịch trình như sau: vào mỗi ngày sẽ đi kiểm tra mọi cây cầu trên đường đi từ đảo a đến đảo b.

Tuy nhiên, lịch trình đó khá là phi khoa học. Thực hiện, xong rồi, Pirate mới ngớ ra là không biết mình có bỏ sót cây cầu nào không?

Dữ liệu vào: Từ tệp văn bản KBUILD.INP

+ Dòng thứ nhất: số nguyên N - số hòn đảo.

+ N - 1 dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b - có một cây cầu dừa nối đảo a và đảo b.

+ Dòng thứ N + 1: số nguyên M - số ngày kiểm tra.

+ M dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b - ngày hôm đó, Pirate sẽ kiểm tra các cây cầu trên đoạn đường từ đảo a đến đảo b.

Dữ liệu ra: Ghi vào tệp văn bản KBUILD.OUT Một số nguyên duy nhất thể hiện số cây cầu chưa được kiểm tra.

Giới hạn: + 1 ≤ N, M ≤ 200000

Ví dụ:

KBUILD.INP	KBUILD.OUT
6 1 2 2 3 2 4 4 5 4 6 2 3 6 5 6	1

Giải thích:  Ngày thứ nhất, Pirate kiểm tra các cây cầu (2, 3), (2, 4) và (4, 6). Ngày thứ hai, anh kiểm tra các cây cầu (5, 4) và (4, 6). Cây cầu duy nhất chưa được kiểm tra là (1, 2).

Làm quen bạn mới

Nguồn: http://vn.spoj.com/problems/FSELECT/

Sau khi tham dự IOI và OLPSV, Nguyên chuyển đến một ngôi nhà mới. Khu nhà mới của Nguyên có N người bạn hàng xóm ( N ≤ 200000). Vì dễ bị nhầm nên Nguyên đánh số các bạn ấy từ 1 đến N. Giữa các ngôi nhà có đường đi tạo thành cây. Khoảng cách giữa hai căn nhà kề nhau là 1 đơn vị. Có K cuộc hẹn ( K ≤ N/2) được Nguyên đưa ra để làm quen với các bạn mới. Để tính toán chi phí mời các bạn, Nguyên muốn biết xem khoảng cách xa nhất của 2 ngôi nhà trong một cuộc hẹn là bao nhiêu ? Bạn hãy giúp Nguyên giải quyết vấn đề này.

Dữ liệu vào: từ tệp văn bản: FSELECT.INP

- Dòng 1 gồm 2 số N và K.

- N dòng tiếp theo, dòng thứ i gồm 2 số x y. Trong đó x là thứ tự của cuộc hẹn mà bạn thứ i tham gia, y là nhà hàng xóm của bạn thứ i. Nếu y = 0 thì đó là gốc của khu dân cư (có thể hiểu là gốc của cây).

Dữ liệu ra: Ghi vào tệp văn bản FSELECT.OUT

Gồm K dòng, dòng thứ i thể hiện đường đi xa nhất tìm được giữa 2 ngôi nhà của 2 người bạn trong cuộc hẹn thứ i.

Ví dụ:

FSELECT.INP	FSELECT.OUT
6 2 1 3 2 1 1 0 2 1 2 1 1 5	3 2

Giải thích:

-3-

|

1

/ | \

2 4 5

    |

    -6-

Trong cuộc hẹn thứ 1 gồm 3 bạn là bạn số 1, số 3 và số 6. Khoảng cách xa nhất giữa 2 ngôi nhà trong cuộc hẹn thứ 1 là 3 (giữa nhà bạn số 3 và số 6). Tương tự, cuộc hẹn thứ 2 gồm 3 bạn số 2, số 4 và số 5. Khoảng cách xa nhất là 2.

LCA - Lowest Common Ancestor

Nguồn: http://www.spoj.com/problems/LCA/

Cho T là một cây gồm N nút. Tổ tiên chung gần nhất (LCA) của hai nút u và v được định nghĩa là nút thấp nhất trong T mà có cả u và v làm con cháu. Nhiệm vụ của bạn trong bài này là tìm LCA của 2 nút bất kỳ trong T.

Dữ liệu vào: Từ tệp văn bản LCA.INP

+ Dòng đầu tiên là số lượng TestCase. Mỗi TestCase bắt đầu là một số nguyên N là số lượng nút trong cây (1<=N<=1000), các nút được đánh số từ 1 đến N. N dòng tiếp theo, dòng thứ i bắt đầu là M cho biết số lượng các nút con của nút thứ i (0<=M<=999).

Dòng tiếp theo là một số nguyên Q cho biết số lượng câu hỏi cần trả lời. Tiếp theo là Q (1<=Q<=1000) dòng mỗi dòng ghi 2 số nguyên u và v và yêu cầu tìm LCA của 2 nút u và v trong cây T.

Dữ liệu vào luôn có duy nhất 1 nút là nút gốc của cây T và không có chu trình.

Dữ liệu ra: Ghi vào tệp văn bản LCA.OUT

Với mỗi TestCase ghi Q+1 dòng

+ Dòng đầu tiên ghi “Case C:” trong đó C là thứ tự của Testcase bắt đầu từ 1

+ Q dòng tiếp theo mỗi dòng ghi LCA của u và v tương ứng trong Input

Ví dụ:

LCA.INP	LCA.OUT
1 7 3 2 3 4 0 3 5 6 7 0 0 0 0 2 5 7 2 7	Case 1: 3 1

Thuật toán LCA - CODE