My Road to ICPC World Finals 2020: tháng 1 2016

[Chưa hoàn thiện] [Đồ thị] [CHD] [Codefun] CHD5J

Đề bài
Cho số n (n<=1000000) và dãy a. Trông đồ thi đỉnh i được nối với đỉnh j khi a[i]<a[j] và i>j. Tìm số lượng thành phần liên thông và liệt kê các đỉnh theo thứ tự tăng dần theo số hiệu trong từng thành phần liên thông.
(đề bài hoàn chỉnh chưa có).
Hướng làm
Do n lớn nên độ phức tạp chấp nhận được là O(nlogn) trở xuống
Để dễ hiểu ta coi mỗi phần tử của mảng a là một đỉnh.
Gọi d[i] là vị trí của đỉnh mang giá trị i trong mảng a.
Xét các đỉnh theo thứ tự giảm dần theo giá trị, ta có các đỉnh đã xét luôn có giá trị cao hơn các đỉnh chưa xét.
Gọi p là vị trí mong muốn, số lượng thành phần liên thông là tplt, vị trí có số hiệu thấp nhất là m ban đầu đặt p = n, tplt = 0, m = n
Với i từ n xuống 1
Nếu d[i]=p thì
tăng tplt;
đánh dấu vị trí p;
p = m-1;
m = p;
không thì
nếu d[i]<m thì m=i
In tplt
Với i từ 1 đến n
Nếu p được đánh dấu thì in số lượng đỉnh trong thành phần liên thông tiếp theo
In p;
Thực tế ta còn phải dùng khá nhiều biến nữa để thực hiện yêu cầu đề bài.
Giải thích:
Các đỉnh nằm sau đỉnh có số hiệu thấp nhất mà chưa được xét luôn có số hiệu thấp hơn nên sẽ nối với đỉnh có số hiệu thấp nhất đó nên sẽ cùng thành phần liên thông với đỉnh đó.
Độ phức tạp: O(n).
Code C++

Nhãn: CHD, CHD5J, Codefun, Đồ thị

[Chưa hoàn thiện] [Quy hoạch động] [CHD] [Codefun] Sum of Digits

Đề bài
Hướng làm
Gọi f[n] là số số có tổng các chữ số bằng s từ 0 đến n, có kết quả res = f[b]-f[a-1].
Phần sau tham khảo của templatetypedef , có sửa lại cho đúng
Gọi dp[n,d,k] là số số có n chữ số, bắt đầu bằng d (d có thể bằng 0) và có tổng các chữ số bằng k, có
dp[0,k,s] = 0
dp[1,s,s] = 1 với 0<=s<=9
dp[1,k,s] = 0 với k<>s hoặc 9<s
dp[1,k,s] = 0 với s<0
dp[d,k,s] = sum {dp[d-1,i,s-k]} với i chạy từ 0 đến 9
Ta tính f[n] như sau
B1: f[n] = sum{dp[l,i,s]} với l là số lượng chữ số của n, i chạy từ 0 đến d[i] với d[i] là chữ số thứ i của n
B2: s = s - d[1]
B3: Với i chạy từ 2 đến n
Với j chạy từ d[i]+1 đến 9
f[n] = f[n] - dp[l-i+1,j,s]
s = s-d[i]
Code C++

Nhãn: CHD, Codefun, HackerEarth, Quy hoạch động, Sum of Digits

[Quy hoạch động] [SPOJ] LQDGONME

Đề bài
Hướng làm (có tham khảo bên traitaodo)
Code

Nhãn: LQDGONME, Quy hoạch động, SPOJ

[Quy hoạch động] [SPOJ] COUNTPL

Đề bài
Hướng làm
Bước 1:
Tham khảo Nguyễn Hoành Tiến, đã sửa lại cho đúng
Dùng mảng F[i, j] có ý nghĩa: F[i, j] = true/false nếu đoạn gồm các kí tự từ i đến j của S có/không là palindrome.
Ta có công thức là:
F[i, i] = True
F[i, j] = (F[i+1, j-1] or (j-i=1)) ( nếu S_i = S_j )
F[i, j] = False; ( nếu S_i <> S_j )
Bước 2:
Gọi dp[i] là kết quả nếu chỉ xét xâu s[1..i].
Ta có dp[i]=dp[j-1]+1 với dp[j-1] nhỏ nhất và thỏa mãn j<=i và f[j,i] (giống bài NKREZ)
Code

Nhãn: COUNTPL, Quy hoạch động, SPOJ

[Chưa hoàn thiện] [Quy hoạch động] [VM] [SPOJ] LSFIGHT

Đề bài
Ta chuẩn hóa lại dữ liệu như sau:
Nếu i thắng k và k thắng j thì i có thể thắng j.
Sau đó đếm số người có khả năng thắng tất cả những người còn lại.
Code (96 điểm SPOJ)
Vẫn tiếp tục nghĩ...

Nhãn: LSFIGHT, Quy hoạch động, SPOJ, VM

[Quy hoạch động] [SPOJ] DTDOI

Đề bài
Dễ có công thức truy hồi
f[i] = min(f[i],f[i-a[j]]+1) với i là số tiền cần đổi, khởi tạo f[i]=oo (dương vô cùng).
Tuy vậy, do s quá lớn nên ta tham bằng cách đổi gần hết s bằng mệnh giá lớn nhất, sau đó quy hoạch động phần tiền thừa còn lại.
Code

Nhãn: DTDOI, Quy hoạch động, SPOJ

[Quy hoạch động] [COI] [SPOJ] MBLAST

Đề bài
Hướng làm (có tham khảo bên traitaodo)
Lưu ý: Test có thể có dấu cách cuối 2 xâu nên ta phải xử lí.
Code

Nhãn: COI, MBLAST, Quy hoạch động, SPOJ

[Quy hoạch động] [SPOJ] NKREZ

Đề bài
Hướng làm
Sắp xếp lại các yêu cầu theo thời điểm đầu.
Gọi f[i] là thời gian lớn nhất hội trường sử dụng khi chỉ nhận yêu cầu i và các yêu cầu trước đó, sử dụng hai vòng lặp lồng nhau (xem bài COUNTPL) ta dễ dàng tìm được f[i].
Kết quả là max(f[1..n]).
Code

Nhãn: NKREZ, Quy hoạch động, SPOJ

[Quy hoạch động] [VM] [SPOJ] VSTEPS

Đề bài
Hướng làm
Tạo mảng boolean l đánh dấu các bậc thang bị lủng.
Theo quy tắc cộng, dễ có công thức truy hồi
f[i]=0 nếu bậc i bị lủng
f[i]=f[i-1]+f[i-2] nếu bậc i không bị lủng.
Code

Nhãn: Quy hoạch động, SPOJ, VM, VSTEPS

[Quy hoạch động] [SPOJ] C11KM

Đề bài
Hướng làm (có tham khảo của onlylove97, đã sửa lại cho đúng)
Gọi f[i] là tổng số phiếu có thể có khi tới ngày thứ i, d[i][j] là chi phí nhỏ nhất khi mua tới mặt hàng thứ i, còn j phiếu
->d[i][j]=min

d[i-1][j]+p[i] (không sử dụng phiếu mua hàng, điều kiện j<=f[i-1])
d[i-1][j-1]+p[i] (có thêm một phiếu, điều kiện p[i]>100 và j>0)
d[i-1][j+1] (sử dụng phiếu mua hàng,điều kiện j<f[i-1]).

kết quả min(d[n][ 0.. f[n] ]).
Code

Nhãn: C11KM, Quy hoạch động, SPOJ

[Quy hoạch động] [SPOJ] C11CAVE

Đề bài
Hướng làm:
B1: Xây dựng mảng a
- Với mỗi măng đá, tăng a[i] lên 1 với i là độ cao điểm đầu của măng đá (tính từ dưới đất) và giảm a[j+1] xuống 1 với j là độ cao điểm cuối măng đá (cũng tính từ dưới đất).
B2: Cộng dồn lại (cách cộng dồn bạn từ nghĩ hoặc xem code, mẹo này mình tham khảo của Triệu Mẫn ở một bài khác) để a[i] trở thành số măng đá đi qua mức i.
B3: Tìm những gì đề bài yêu cầu (có thể kết hợp vào B2).
Lưu ý mảng a khai báo rộng ra một chút để tránh tràn.
Bài này mình tự nghĩ :)
Code

Nhãn: C11CAVE, Quy hoạch động, SPOJ

[Quy hoạch động] [SPOJ] AMSSEQ

Đề bài
Hướng làm:
Gọi f[i] là số điểm lớn nhất có thể khi tới ô i.
f[0]=0; f[1]=max(0,a[i]);
Khởi tạo f[i]=10^(-9), sau đó tính f[i]=max(f[i],f[j]+a[i]) với i chạy từ 2 cho đến n, j chạy từ i-k đến i-1.
Kết quả là max(f[i]);
Bài này mình có tham khảo bên kienthuc24h
Code

Nhãn: AMSSEQ, Quy hoạch động, SPOJ

[Quy hoạch động] [USACO] [SPOJ] VCOWFLIX

Đề bài
Hướng làm:
Tạo một mảng chứa các tổng đang có và một mảng truy vết (trace) để tính số con bò để tạo ra tổng ấy.
Code

Nhãn: Quy hoạch động, SPOJ, USACO, VCOWFLIX

[Chưa hoàn thiện] [DFS và BFS] [VOI] [SPOJ] ROBOCON

Đề bài
Hướng làm:
Tưởng bài này giống bài QBAGENTS, tuy vậy do giới hạn quá lớn nên ta không thể dùng mảng 5 chiều để quy hoạch động được.
Cách làm có tham khảo bên onlylove97
Loang lần lượt từng con robot cho để biết tại thời điểm t các con robot có thể ở vị trí nào, nếu có một ô mà cả hai có thể gặp nhau thì dừng loang, in ra t. Lưu ý các ô có thể đi qua đi lại nhiều lần.
Code (90 điểm SPOJ)

Nhãn: DFS và BFS, ROBOCON, SPOJ, VOI

[DFS và BFS] [Quy hoạch động] [Mảng 3 chiều] [SPOJ] QBAGENTS

Đề bài
Hướng làm:
Tham khảo vnspoj.blogspot.com
Gọi F[u,v,k] là thời gian min để người 1 đến u, người 2 đến v và đến lượt người k đi tiếp. Loang từ F[s,t,1], mỗi lượt luân phiên nhau từng người. Ban đầu khởi tại F[i,j,k] =maxValue. Kết quả là min(F[u,u,1]). (tùy từng cách code là cộng tiếp thời gian luân phiên hay cộng thời gian theo lượt hai người mà F[u,u,1]/2 hay F[u,u,1]).Code

Nhãn: DFS và BFS, Mảng 3 chiều, QBAGENTS, Quy hoạch động, SPOJ

[DFS và BFS] [Tìm kiếm nhị phân] [USACO] [SPOJ] MTWALK

Đề bài
Hướng làm:
Chặt nhị phân kết quả, sau đó DFS thử xem có đi được không.
Tuy vậy việc kiểm tra độ cao chênh lệch của đường đi quá phức tạp, nên với mỗi độ cao nhỏ nhất, ta tìm độ cao lớn nhất tương ứng với kết quả mình đang xét, sau đó tìm đường đi có độ cao nằm giữa khoảng này (phần này mình tham khảo bên kienthuc24h)
Mình không chặt nhị phân trong code do kết quả cứ ra sai.
Code

Nhãn: DFS và BFS, MTWALK, SPOJ, Tìm kiếm nhị phân, USACO

[DFS và BFS] [USACO] [SPOJ] NKGUARD

Đề bài
Hướng làm:
Tìm các thành phần liên thông có cùng độ cao trong bảng, sau đó kiểm tra xem thành phần liên thông đó có phải là đỉnh đồi hay không bằng cách kiểm tra độ cao của các thành phần liên thông liền kề.
Cách làm này mình có tham khảo blog của traitaodo
Code

Nhãn: DFS và BFS, NKGUARD, SPOJ, USACO

[DFS và BFS] [VOI] [SPOJ] STABLE

Đề bài
Hướng làm:
- Sử dụng mảng a làm ma trận kề để tránh dữ liệu lặp, đồng thời chuyển thành danh sách kề để giảm độ phức tạp của BFS.
- Dùng BFS tìm số đường đi ngắn nhất đến từng đỉnh, nếu tìm được 2 đường đi ngắn nhất thì tăng biến đếm, cộng thêm nhận xét từ test ví dụ: nếu u ổn định mà u nằm trên đường đi ngắn nhất từ s đến v thì v ổn định, ta giải được bài này.
- Do trên SPOJ có thêm vài giới hạn về bộ nhớ nên ta phải dùng con trỏ để giảm bộ nhớ sử dụng, cũng như loại bỏ mảng a ở trên (thay thế bằng hàm found).
Code

Nhãn: DFS và BFS, SPOJ, STABLE, VOI

[Chưa hoàn thiện] [DFS và BFS] [VOI] [SPOJ] STNODE

Đề bài
Hướng làm được 83,33 điểm
BFS tìm 1 đường đi ngắn nhất bất kì từ s đến t, sau đó bỏ dần từng đỉnh rồi DFS thử xem có đến được không.
Thuật chuẩn theo đồn đoán trên mạng là dùng luồng, nhưng cách cài đặt rất phức tạp nên ta sẽ cài sau :)
Code

Nhãn: DFS và BFS, SPOJ, STNODE, VOI

[DFS và BFS] [Tham lam] [vCoder] [SPOJ] V8ORG

Đề bài
Hướng làm:
DFS từng phần tử như sau:
- Duyệt hết tất cả các thành viên "con"
- Nếu số thành viên "con" của nó vẫn lớn hơn k thì bắt giữ thành viên đó, cập nhập lại số "con" của các thành viên chỉ huy thành viên đó.
Chứng minh đã có trong blog của traitaodo
Code

Nhãn: DFS và BFS, SPOJ, Tham lam, V8ORG, vCoder

My Road to ICPC World Finals 2020

Thứ Sáu, 29 tháng 1, 2016

[Chưa hoàn thiện] [Đồ thị] [CHD] [Codefun] CHD5J

Thứ Tư, 27 tháng 1, 2016

[Chưa hoàn thiện] [Quy hoạch động] [CHD] [Codefun] Sum of Digits

Chủ Nhật, 24 tháng 1, 2016

[Quy hoạch động] [SPOJ] LQDGONME

Thứ Tư, 20 tháng 1, 2016

[Quy hoạch động] [SPOJ] COUNTPL

[Chưa hoàn thiện] [Quy hoạch động] [VM] [SPOJ] LSFIGHT

Thứ Hai, 18 tháng 1, 2016

[Quy hoạch động] [SPOJ] DTDOI

[Quy hoạch động] [COI] [SPOJ] MBLAST

[Quy hoạch động] [SPOJ] NKREZ

Thứ Bảy, 16 tháng 1, 2016

[Quy hoạch động] [VM] [SPOJ] VSTEPS

[Quy hoạch động] [SPOJ] C11KM

[Quy hoạch động] [SPOJ] C11CAVE

Thứ Tư, 13 tháng 1, 2016

[Quy hoạch động] [SPOJ] AMSSEQ

Thứ Hai, 11 tháng 1, 2016

[Quy hoạch động] [USACO] [SPOJ] VCOWFLIX

Thứ Bảy, 9 tháng 1, 2016

[Chưa hoàn thiện] [DFS và BFS] [VOI] [SPOJ] ROBOCON

Thứ Tư, 6 tháng 1, 2016

[DFS và BFS] [Quy hoạch động] [Mảng 3 chiều] [SPOJ] QBAGENTS

Thứ Ba, 5 tháng 1, 2016

[DFS và BFS] [Tìm kiếm nhị phân] [USACO] [SPOJ] MTWALK

Thứ Hai, 4 tháng 1, 2016

[DFS và BFS] [USACO] [SPOJ] NKGUARD

Chủ Nhật, 3 tháng 1, 2016

[DFS và BFS] [VOI] [SPOJ] STABLE

Thứ Bảy, 2 tháng 1, 2016

[Chưa hoàn thiện] [DFS và BFS] [VOI] [SPOJ] STNODE

[DFS và BFS] [Tham lam] [vCoder] [SPOJ] V8ORG

Giới thiệu về tôi

Liên kết

Bài đăng trước đó

Lưu trữ