[Tìm kiếm nhị phân] [RMQ] [Cây IT] [Binary Search] [Segment Tree] [Codeforces] R2D2 and Droid Army

Đề bài

Ý tưởng (cập nhật sau)

Lời giải (cập nhật sau)

Code (cây IT, Java)

Code (RMQ, Java)

[Số học] [Tô màu bàn cờ] [Number Theory] [Chessboard Coloring] [AtCoder] AGC027-D Modulo Matrix

Đề bài

Tóm tắt đề bài

Tạo bảng kích thước n*n sao cho các số trong bảng đôi một khác nhau và với mọi hai số (x,y) kề cạnh, ta có max(x,y)%min(x,y) = m với m là hai số nguyên dương nào đó. Ngoài ra, các số trong bảng không được vượt quá 10^15.

Ý tưởng

Tô màu kiểu bàn cờ cho bảng, sau đó điền hết ô đen với các số bất kì, khi đó số ở ô trắng sẽ bằng bội chung lớn nhất của các ô đen kề với nó + 1.

Lời giải

Để đảm bảo các số trong bảng đôi một khác nhau, với mỗi đường chéo đen chính và đường chéo đen phụ, ta gán với đường chéo đó một số nguyên tố khác nhau. Mỗi ô đen sẽ có giá trị bằng tích của hai số nguyên tố được gán với hai đường chéo đi qua ô đó. Khi đó, số ở ô trắng sẽ bằng tích của bốn số nguyên tố nguyên tố của bốn đường chéo đen giáp với nó cộng 1. Dễ dàng nhận thấy rằng số ở các ô là khác nhau.

(Lưu ý ta gán số nguyên tố cho cả những đường chéo nằm ngoài bảng để đảm bảo các ô trắng ở mép không bị trùng nhau)

Ta thấy trong trường hợp xấu nhất (n = 500), ta chỉ có khoảng 1000 đường chéo đen. Do số nguyên tố thứ 1000 bằng 7919, ta thấy chỉ cần gán số nguyên tố sao cho các đường chéo chính có số nguyên tố nhỏ sẽ giáp với các đường chéo phụ có số nguyên tố lớn là hoàn toàn có thể thỏa mãn được điều kiện các số trong bảng không vượt quá 10^15.

Code (Java)

[Quy hoạch động] [Tổ hợp] [Bao hàm - Loại trừ] [Đường tròn] [Dynamic Programming] [Combinatorics] [Inclusion-Exclusion] [Circle] [AtCoder] AGC028-D Chords

Đề bài

Tóm tắt đề bài

Cho 2N điểm cách đều nhau trên đường tròn và K cặp điểm được nối sẵn, tính tổng của tổng số thành phần liên thông của các cách nối N-K cặp điểm còn lại.

Ý tưởng

Đếm số lần xuất hiện của các thành phần liên thông có i là điểm có chỉ số nhỏ nhất và j là điểm có chỉ số lớn nhất, ta gọi thành phần liên thông như vậy là thành phần (i,j).

Lời giải

Ta có thể sử dụng phương pháp quy hoạch động để tính số loại thành phần (i,j).

Đầu tiên, gọi x là số điểm chưa được nối trong số các điểm có chỉ số từ i đến j, ta thấy số cách nối các điểm này là (x-1)*(x-3)*...*1 (nếu x chẵn, nếu x lẻ thì ta không có cách nối). Tuy nhiên, ta thấy rằng không phải bất cứ cách nối nào cũng cho ta đúng một loại thành phần (i,j) (vì có thể có trường hợp nối thành hai thành phần (i,k) và (k,j) với k nằm giữa i và j). Do đó, ta phải tìm cách loại các trường hợp này ra.

Sau một hồi suy nghĩ, gọi dp(i,j) là số loại thành phần (i,j), ta có công thức quy hoạch động
dp(i,j) = (số cách nối các điểm từ i đến j) - tổng các (dp(i,k) * (số cách nối các điểm từ k đến j)) với k chạy từ i đến j.

Lưu ý rằng đầu tiên ta phải kiểm tra xem có điểm nào nằm giữa i và j nối ra ngoài đoạn từ i đến j không, vì nếu có thì ta không thể có được thành phần (i,j).

Mỗi loại thành phần (i,j) sẽ xuất hiện trong (số cách nối các điểm nằm ngoài đoạn i đến j) cách nối, do đó đáp án sẽ là tổng các (dp(i,j)*(số cách nối các điểm nằm ngoài đoạn i đến j)).

Code (Java)

[Quy hoạch động] [UVa] 10039

Đề bài
Hướng làm
Gọi dp[i][j] là thời gian xuất phát muộn nhất để đến thành phố i vào lúc j, sau đó quy hoạch động.
Code

[Quy hoạch động] [Tham lam] [UVa] 757

Đề bài
Hướng làm
Bước 1: Quy hoạch động thời gian đi từ hồ 1 đến hồ i
Bước 2:
Giả sử ta chỉ câu cá ở các hồ từ hồ 1 đến hồ i
Ta dễ dàng tính được thời gian câu thực tế sau khi trừ đi thời gian di chuyển.
Với mỗi 5 phút, ta xem trong 5 phút ấy câu ở hồ nào lợi nhất thì phân bổ thời gian 5 phút vào hồ đó. Để giảm độ phức tạp, ta có thể dùng heap.
Code

[Quy hoạch động] [Bitmask] [Floyd] [UVa] 1281

Đề bài
Hướng làm:
Bước 1: Dùng thuật toán Floyd tìm đường đi ngắn nhất giữa mọi cặp đỉnh
Bước 2: Chia đường đi thành 4 phần rồi quy hoạch động giống dạng TSP (Traveling Saleman)
Code

[Quy hoạch động] [UVa] 11259

Đề bài
Gọi dp[i] là số cách đổi i đồng, với số lượng mỗi đồng không giới hạn.
Để có được kết qủa, ta dùng phương pháp bao hàm và loại trừ, tức là trừ các cách đổi i đồng thành nhiều hơn d[1] đồng 1, nhiều hơn d[2] đồng 2, ... rồi cộng tiếp số cách đổi i đồng thành nhiều hơn d[1] đồng 1 và d[2] đồng 2,... (xem kĩ hơn trong code).
Code