Go Back   Cựu Học Sinh Lê Quý Đôn - Long An > :: Góc Học Tập :: > Tin học > Tin học phổ thông

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

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

this thread has 6 replies and has been viewed 8100 times

Gởi Ðề Tài Mới Trả lời
 
Ðiều Chỉnh Xếp Bài
Old 28-02-2009, 08:46 PM   #1
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Đề thi HSG QUốc Gia 2009 - môn Tin học

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. ]
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 04-03-2009, 08:38 AM   #2
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Đề 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.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 04-03-2009, 08:47 AM   #3
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học

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.
__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 04-03-2009, 09:00 AM   #4
Hồ sơ
myhanh
 
myhanh's Avatar
 
Tham gia ngày: Dec 2004
Cư ngụ: Love Planet
Tuổi: 43
Số bài viết: 7,404
Tiền: 0
Thanks: 2,119
Thanked 5,463 Times in 2,040 Posts
myhanh is on a distinguished road
Default Ðề: Đề thi HSG QUốc Gia 2009 - môn Tin học

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.



__________________
Necessity is the mother of in(ter)vention.
Speak softly & carry a big stick.
My Technical Blog
myhanh is offline   Trả Lời Với Trích Dẫn
Old 13-03-2009, 07:09 PM   #5
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: Đề 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)
Code:
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 is offline   Trả Lời Với Trích Dẫn
Old 13-03-2009, 07:14 PM   #6
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: Đề 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 ). 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))

thay đổi nội dung bởi: duyhung123abc, 13-03-2009 lúc 07:17 PM.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Old 13-03-2009, 07:15 PM   #7
Hồ sơ
duyhung123abc
Senior Member
 
duyhung123abc's Avatar
 
Tham gia ngày: Jun 2008
Số bài viết: 206
Tiền: 25
Thanks: 10
Thanked 45 Times in 40 Posts
duyhung123abc is on a distinguished road
Default Ðề: Đề 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.

thay đổi nội dung bởi: duyhung123abc, 13-03-2009 lúc 07:26 PM.
duyhung123abc is offline   Trả Lời Với Trích Dẫn
Trả lời


Ðiều Chỉnh
Xếp Bài

Quyền Sử Dụng Ở Diễn Ðàn
Bạn không được quyền gởi bài
Bạn không được quyền gởi trả lời
Bạn không được quyền gởi kèm file
Bạn không được quyền sửa bài

vB code đang Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt
Chuyển đến

Chủ đề tương tự
Ðề tài Người Gởi Chuyên mục Trả lời Bài mới gởi
Kiến thức cơ bản về bộ máy nhà nước phanphuong Khoa học Xã hội 46 31-07-2008 02:24 PM
Việt Nam đăng cai Đại lễ Phật Đảng Liên hiệp quốc 2008 YourFriend ..:: Điểm tin ::.. 3 08-05-2008 11:36 PM
3. Viết cho đàn em magicboy Nội san 7 16-03-2007 10:48 PM
Học sinh đoạt giải quốc gia muốn vào ĐH, CĐ vẫn phải dự thi LeGiang ..:: Điểm tin ::.. 0 03-02-2007 11:02 AM
Đọc báo: Tham Nhũng toi&m ..:: Điểm tin ::.. 5 01-01-1970 07:00 AM


Website sử dụng phần mềm vBulletin phiên bản 3.6.8
do Công ty TNHH Jelsoft giữ bản quyền từ 2000 - 2024.
Múi giờ GMT +7. Hiện tại là 04:49 PM.

Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này

Tự động[F9]TELEX VNI VIQR VIQR* TắtKiểm chính tảDấu cũ
phan mem quan ly ban hang | thuê vps