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

[duyhung123abc]

bài 1:
[Đăng nhập để xem liên kết. ]

bài 2:
[Đăng nhập để xem liên kết. ]

bài 3:
[Đăng nhập để xem liên kết. ]

[myhanh]

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.

[myhanh]

Bài số 1 là bài toán quy hoạch động.
Hueristic của anh dùng ở đây là con số hàng lẻ là con số càng lớn càng tốt, con số hàng chẵn thì càng bé càng tốt và dãy số tìm được càng dài càng tốt.
Theo anh bài này sử dụng vét cạn+nhánh cận.

[myhanh]

Bài số 3 chỉ cần vét cạn và nhánh cận.
Khi đặt chũ số Cj vào vị trí thứ i trong C mới cần phải thoả điều kiện:
Cj > Ai, Cj >Bi
Cj < An-i, Cj < Bn-j
Như vậy chương trình chạy tối đa 6^n thôi.

[duyhung123abc]

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)

max_am:=0;
max_duong:=A[1];
for i:=2 to n do
  begin
    am:=max_duong - A[i];
    duong:=max_am + A[i];
    if am>max_am then max_am:=am;
    if duong>max_duong then max_duong:=duong;
  end;
writeln(max(max_duong,max_am));

[duyhung123abc]

Bài 2:
Ý em hoàn toàn giống như anh myhanh (nhưng minpath từ s đến t chỉ BFS thôi ). 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))

[duyhung123abc]

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.