Đề thi HSG QUốc Gia 2009 - môn Tin học
 

bài 1:
[Only registered and activated users can see links. Click Here To Register...]

bài 2:
[Only registered and activated users can see links. Click Here To Register...]

bài 3:
[Only registered and activated users can see links. Click Here To Register...]

Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học
 

bài số hai là bài lý thuyết đồ thị quá dễ dàng đúng không?
*a là nút xung yếu khi a thuộc đường đi ngắn nhất từ s=>t.
*loại a ra khỏi graph thì không tìm được đường đi từ s=>t.
Giải thuật dễ nhìn thấy nhất là chạy Dijisktra 1 lần
và giải thuật tìm đường đi (BFS,DFS).
Một giải thuật khác là tìm tất cả các đường đi từ s=>t sau đó tìm các nút xung yếu theo định nghĩa là nút xuất hiện trong tất cả các đường này.
(Phải chỉ ra không cần tìm những đường đi có chứa chu trình)
Không biết DH có cao kiến gì khác không.

Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học
 

Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học
 

Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học
 

Bài số 1:
Em nhận xét là khi xét tới thằng thứ i thì ta có 2 trường hợp:
_ Đặt dấu + trước A_i: cái này thì mình cần biết giá trị max_am (tức là tổng lớn nhất mà số cuối cùng của tổng đó là số âm)
_ Đặt dấu - trước A_i: cái này thì mình cần biết giá trị max_duong (tương tự max_am)

Vậy chỉ cần chạy 1 vòng lặp vừa sử dụng 2 biến đó vừa cập nhật lại giá trị cho nó => độ phức tạp O(n)

Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học
 

Bài 2:
Ý em hoàn toàn giống như anh myhanh (nhưng minpath từ s đến t chỉ BFS thôi :D). Nhưng cách này có thể die 1 số test vì chương trình chạy chậm.
Có 1 cách nhanh hơn là dựa trên nhận xét:
_Giả sử các đỉnh trên đường đi ngắn nhất lần lượt là s(1),s(2),...,s(k)
_Rõ ràng nếu từ s(1) ta có thể đi đến s(i) nào đó thì các đỉnh từ s(2) đến s(i-1) chắc chắn ko phải nút xung yếu (vì tồn tại đường đi s(1),s(i),s(i+1),...,s(k))

Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học
 

Bài 3: em chưa biết cách nào tốt. Cách của em làm lúc thi do suy nghĩ ko cẩn thận nên cách đó ko ổn, phải chờ test của bộ thôi, nếu rơi nhiều vào trường hợp đó thì em die. Em tự tin quá ko ăn 60% test dễ (60% này N<=10). Cách làm để ăn 60% test là duyệt đệ quy mọi hoán vị rồi cập nhật kq (độ phức tạp O(N!) )

to Myhanh: N<=200 000 thì 6^n đâu làm đc gì anh, thậm chí 60% cũng khó ăn. :(