Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
ngày thi 1 (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 4
CHỦ ĐỀ - ngày thi 1
#70038
phamanhtu (Thành viên)
phamanhtu1996-
Biết code binary-indexed tree
Bài viết: 20
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
Sol 3 bài của mình:
- Bài 1:
+ Nhận xét:
- k <= 6 thì luôn có cách ăn hết.
- Hậu và Voi ăn theo đường chéo, nếu ta muốn kiểm tra một ô có bị ăn hay không thì chỉ việc so sánh tổng và hiệu 2 tọa độ.
- Hậu và Xe ăn theo đường thẳng, nếu ta muốn kiểm tra một ô có bị ăn hay không thì chỉ việc so sánh hàng và cột.
- Muốn kiểm tra mã có ăn một ô hay không thì ta cần kiểm tra tổng độ chênh lệch 2 tọa độ xem có bằng 3 hay không.
+ Từ đó ta có thuật toán:
- Xét chỉnh hợp lặp chập 4 của (64-k).
- Kiểm tra mỗi món quà có bị ăn hay không và cập nhật kết quả.
+ k*(64-k)^4
- Bài 2:
+ Xét một chiều của hình chữ nhật (r), sau xét một cột trên bảng A (i), 1 cột bên bảng B (u).
+ Tìm hình con chung liên tiếp dài nhất trên hai vùng. (i->i+r-1 và u->u+r-1).
+ Đpt n^6, khởi tạo trước nên đpt còn n^5.
- Bài 3:
+ Dùng Kruskal + Heap.
+ Sau khi thay đổi trọng số của một số cạnh thì ta tìm cây khung nhỏ nhất trên đồ thị đó.
+ Sau ta tìm cây khung lần 2, lần này ta nhận cạnh cần kiểm tra vào cây khung trước, sau tìm thêm n-2 cạnh để tạo thành cây khung nhỏ nhất.
+ So sánh độ lớn hai cây khung để trả lời kết quả.
+ đpt t*q*mlog(m)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70039
mathias (Thành viên)
chlmathias+2
Biết code binary-indexed tree
Bài viết: 39
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
Theo mọi người đánh giá thì độ khó đề năm nay thế nào? Mình thấy bài 1 khó hơn hẳn bài 1 năm ngoái, bài 3 thì dễ ăn điểm hơn
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70040
Nguyen_Duy_Khanh (Thành viên)
songuku95+25
Không code nữa rồi
Bài viết: 374
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
linuxpro viết:
[quote]
QUOTE:
nntien viết:
QUOTE:
Nguyen_Duy_Khanh viết:
QUOTE:
Mình xin tóm tắt qua đề

Bài 1: Cho hình vuông 8*8 và một số ô chứa các số nguyên dương. Mình phải đặt xe,hậu,tịnh,mã vào những ô không có số nguyên dương. Sau khi đặt xong, những ô bị 1 trong 4 quân đó kiểm soát thì mình được thưởng từng đó điểm. Tính max điểm thưởng



Bài này có tính đến bị chặn quân. Sao trong đề không nói rõ nhỉ!
Bài này dễ ... nhưng dễ bị hiểu sai!!!


Chặn quân chỉ tính trong cờ tướng thôi chứ nhỉ, từ bé đến giờ mình chơi cờ vua chưa thấy cái luật chặn quân nào cả (hoặc là mình chỉ đc dạy như thế thôi) ??!!!


VD
X V 10 10
Thì xe có ăn được 2 con 10 hay không ?

Ý bạn ấy là thế cơ mà cậu
 
Đã lưu IP Đã lưu IP  
 
Y!M: duy_khanh308
  Đã khóa chức năng gửi bài.
#70041
phamanhtu (Thành viên)
phamanhtu1996-
Biết code binary-indexed tree
Bài viết: 20
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
Đề ngày 1 năm nay vừa dài, đọc hoa mắt, vừa khó hiểu, đọc xong thì code dài, khó, bài ít điểm lại không dễ ăn điểm bằng bài cao điểm.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70042
lonely_heart888 (Thành viên)
lonelyheart888
Biết code binary-indexed tree
Bài viết: 22
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
QUOTE:
tuananh93x viết:
QUOTE:
studytolive viết:
QUOTE:
bài 3 e làm Kruskal trong bược sắp xếp cạnh thì ưu tiên cạnh k lên trước. Xong rồi chọn bình thường nếu mà cạnh k đ.c chọn thì nó thuộc 1 trong những cây khung còn không thì sẽ không thuộc cây khung nào hết . Không biết có phải cách anh Tuấn Anh không ?


Chắc ý em là ưu tiên cạnh k trong các cạnh cùng trọng số? Ý anh cũng như thế. Nhưng từ đó có thể thấy ko cần sắp xếp => bớt đi 1 cái log.

Dạ nếu như thế này thì lại gần với cách của em, nhưng em hơi phân vân 1 chỗ, là nếu mình làm thế này liệu có đảm bảo không vì việc có add cạnh k vào hay không lại phụ thuộc vào việc add cạnh nào trước đó, khi union ta chỉ thêm vào cây khung nếu x và y chưa cùng cha, em không có chứng minh được cái này ạ, mong anh chỉ giáo thêm

cái đó mình nghĩ tự thuật toán kruskal đã chứng minh rồi nhỉ
nếu không chọn những cạnh bé hơn trước để chọn cạnh k =>ko phải là cây khung nhỏ nhất
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70043
sirdat_LS (Thành viên)
tranquocdat+26
Không code nữa rồi
Bài viết: 351
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
Nguyen_Duy_Khanh viết:
[quote]linuxpro viết:
QUOTE:
QUOTE:
nntien viết:
QUOTE:
Nguyen_Duy_Khanh viết:
QUOTE:
Mình xin tóm tắt qua đề

Bài 1: Cho hình vuông 8*8 và một số ô chứa các số nguyên dương. Mình phải đặt xe,hậu,tịnh,mã vào những ô không có số nguyên dương. Sau khi đặt xong, những ô bị 1 trong 4 quân đó kiểm soát thì mình được thưởng từng đó điểm. Tính max điểm thưởng



Bài này có tính đến bị chặn quân. Sao trong đề không nói rõ nhỉ!
Bài này dễ ... nhưng dễ bị hiểu sai!!!


Chặn quân chỉ tính trong cờ tướng thôi chứ nhỉ, từ bé đến giờ mình chơi cờ vua chưa thấy cái luật chặn quân nào cả (hoặc là mình chỉ đc dạy như thế thôi) ??!!!


VD
X V 10 10
Thì xe có ăn được 2 con 10 hay không ?

Ý bạn ấy là thế cơ mà cậu

Theo mình thì quan tâm chặn chọt làm cái gì, đề nói thế nào thì làm thế thôi, chẳng nhẽ trúng đạn rồi tra xem đạn nó có phải từ súng quân thù không rồi mới chết à
 
Đã lưu IP Đã lưu IP  
 
Cầu trời mai đề dễ chịu với con
  Đã khóa chức năng gửi bài.
#70044
linuxpro (Thành viên)
linuxpro-
Biết code binary-indexed tree
Bài viết: 25
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
ờ ờ, sorry hiểu sai.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70045
linuxpro (Thành viên)
linuxpro-
Biết code binary-indexed tree
Bài viết: 25
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
nhưng mà đề cho là : " Con Hậu: Khi đặt con hậu lên bàn cờ, nó sẽ khống chế được tất cả các ô thuộc cùng hàng ngang, cột dọc hoặc đường chéo với nó" -> chỉ cần thuộc đường đi của hậu là sẽ bị ăn ( tức là X V 10 10) vẫn đc 20
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#70047
studytolive (Thành viên)
studytolive+5
Super fast coder
Bài viết: 59
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
tuananh93x viết:
QUOTE:
studytolive viết:
QUOTE:
bài 3 e làm Kruskal trong bược sắp xếp cạnh thì ưu tiên cạnh k lên trước. Xong rồi chọn bình thường nếu mà cạnh k đ.c chọn thì nó thuộc 1 trong những cây khung còn không thì sẽ không thuộc cây khung nào hết . Không biết có phải cách anh Tuấn Anh không ?


Chắc ý em là ưu tiên cạnh k trong các cạnh cùng trọng số? Ý anh cũng như thế. Nhưng từ đó có thể thấy ko cần sắp xếp => bớt đi 1 cái log.


ừ nhỉ lúc đấy cuống quá chẳng nghĩ đ.c gì nữa code luôn QS
 
Đã lưu IP Đã lưu IP  
 
So Try
  Đã khóa chức năng gửi bài.
#70048
mathias (Thành viên)
chlmathias+2
Biết code binary-indexed tree
Bài viết: 39
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: ngày thi 1 8 năm trước   (+0)
studytolive viết:
QUOTE:
tuananh93x viết:
QUOTE:
studytolive viết:
QUOTE:
bài 3 e làm Kruskal trong bược sắp xếp cạnh thì ưu tiên cạnh k lên trước. Xong rồi chọn bình thường nếu mà cạnh k đ.c chọn thì nó thuộc 1 trong những cây khung còn không thì sẽ không thuộc cây khung nào hết . Không biết có phải cách anh Tuấn Anh không ?


Chắc ý em là ưu tiên cạnh k trong các cạnh cùng trọng số? Ý anh cũng như thế. Nhưng từ đó có thể thấy ko cần sắp xếp => bớt đi 1 cái log.


ừ nhỉ :| lúc đấy cuống quá chẳng nghĩ đ.c gì nữa code luôn QS :))


Liệu như thế có ăn đc hết 60% không nhỉ :-?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS