Một vài gợi ý Pre ACM PTIT round 3

Problem A: Nguyên tố cùng nhau

Thuật toán : Số học (MOD nghịch đảo), tìm kiếm nhị phân.

Ta có a x b mod k = 1 thì khi đó b là mod nghịch đảo của a, ở đây k = 10^9 + 7 là số nguyên tố nên b = a^(k-2) % k.

Duyệt các phần tử trong mảng a, với mỗi a[i] thì ta tìm được mod nghịch đảo của nó, kiểm tra xem có giá trị mod nghịch đảo đó trong mảng a[] không, nếu có thì tăng kết quả và đánh dấu a[i] và a[j] đã được chọn.

Sử dụng map của stl sẽ rất tiện lợi cho bài toán này.

Problem B: Dãy số Catalan

Thuật toán: Số học, xử lí số nguyên lớn

Ta có thể dễ dàng tìm ra công thức của 

Nhận thấy kết quả sẽ rất lớn nên ta sẽ phải dùng số nguyên lớn để xử lý.

Ta phân tích tử và mẫu thành tích các thừa số nguyên tố với số mũ tương ứng, khi chia tử và mẫu thì chỉ cần trừ số mũ của các thừa số giống nhau. Sau khi đã phân tích xong, chỉ cần dùng số nguyên lớn để nhân các thừa số nguyên tố lại với nhau.

Problem C: Hành tinh tiềm năng

Thuật toán: Cấu trúc dữ liệu

Ta sắp xếp các hành tinh có thứ hạng tăng dần theo tiêu chí 1, việc còn lại là tìm xem trước đó có hành tinh nào có tiêu chí 2 và tiêu chí 3 đều có thứ hạng nhỏ hơn thì hành tinh đó không tiềm năng và ngược lại. Giả sử chỉ xét hai tiêu chí 1 và 2 thì ta cần kiểm tra xem thứ hạng nhỏ nhất trong các hành tinh trước, nếu xét cả 3 thì xem trong hành tinh trước đấy mà có thứ hạng tiêu chí 2 nhỏ hơn hành tinh đang xét thì tìm thứ hạng m thấp nhất theo tiêu chí 3, nếu m nhỏ hơn tiêu chí 3 của hành tinh hiện tại thì hành tinh hiện tại không phải tiềm năng và ngược lại.

Giả sử đang xét hành tinh thứ i thì ta cần tìm giá trị nhỏ nhất theo tiêu chí 3 của các hành tinh đã xét mà có tiêu chí 2 < r2[i] (Dùng cây BIT hay cây Fenwick).

Problem D: Khôi phục hành trình

Thuật toán: Tham lam

f[i][j] chính là cha chung gần nhất của hai nút I và j, đầu tiên ta tìm nút gốc i của cây (là nút mà nút cha gần nhất với tất cả các nút (kể cả chính nó) đều bằng i), loại bỏ nút gốc i ta được các các cây con với nút gốc chính là các nút con của nút i, cứ như thế đến khi không còn cây con nào nữa.

Problem E: Trò chơi với những hạt đậu

Thuật toán: Tham lam

Cách chơi tối ưu: Duyệt từ bên phải về. Nếu tại ô thứ i, số hạt đậu trong đó không chia hết cho i thì đó là trường hợp không thể rải hết.

Problem F: Quyết chiến

Sắp xếp 2 dãy theo thứ tự giảm dần. Gọi dãy thứ nhất là A, dãy thứ 2 là B. Xét tại đỉnh của 2 dãy, nếu phần tử đầu (đỉnh) của A lớn hơn B, loại đỉnh của A khỏi danh sách, ngược lại tăng đếm, loại đỉnh của cả 2 dãy.

code P153PROF PTIT spoj – Quyết chiến

https://kienthuc24h.com/p153prof-ptit-spoj-quyet-chien/

Problem G: Chẵn lẻ

Kiểm tra xem với vị trí pos đã cho thì số đó là chẵn hay lẻ. Nếu số lẻ kết quả là 2 * pos – 1 nêu là chẵn kết quả là 2 * (pos – (pos + 1) / 2).

Problem H: Phòng họp

Thuật toán: LCA (cha chung gần nhất của 2 nút trên cây).

Với mỗi truy vấn u, v, gọi lca = LCA(u, v).

Gọi cnt[i]: trọng lượng cây con gốc i

Với d = level[u] + level[v] – 2 * level[lca] với level[i] là mức của nút i .

Có 2 trường hợp xảy ra:

Nếu d lẻ, không nó nút nào thỏa mãn.

Nếu d chẵn, có 2 trường hợp xảy ra:

– u và v có cùng mức với nhau. Gọi pu là cha thứ d/2 – 1 của u, pv là cha thứ d/2 – 1 của v. Kết quả = n – cnt[pu] – cnt[pv].

– u và v khác mức, coi u luôn là nút có mức lớn hơn. Gọi center là cha thứ d/2 của u.

Kết quả = cnt[center] – cnt[pu].

Tham khảo thêm về thuật toán LCA :

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

Problem I: Mã hóa xâu

Bài toán này khá đơn giản, chỉ cần làm đúng như yêu cầu của đề bài.

Code P153PROI PTIT spoj – Mã hóa xâu:

https://kienthuc24h.com/p153proi-ptit-spoj-ma-hoa-xau/

Problem J: Số cặp nghịch thế

Thuật toán: deque, cấu trúc dữ liệu.

Ta duyệt các dãy con từ trái sang phải.

Giả sử ta đang duyệt dãy còn mà phần phần tử ban đầu là a[i] và có j là vị trí nhỏ nhất mà dãy con từ vị trí i đến j có số lượng cặp nghịch thế >= k. Rõ ràng với a[i+1] và j’, chúng ta không cần phải duyệt lại cả dãy con mới. Do vậy, với a[i+1], ta sẽ tịnh tiến j để tìm j’. Trong lúc dịch chuyển cửa sổ việc cập nhật số cặp nghịch thể thực hiện bằng các sử dụng cây BIT.

P153PROA, P153PROB, P153PROC, P153PROD, P153PROE, P153PROF, P153PROG, P153PROH, P153PROJ PTIT spoj