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)

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

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

Đề 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.

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

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 à

ờ ờ, sorry hiểu sai.

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

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

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ỉ :-?