Note giải đề HSG THPT tỉnh Khánh Hòa - 2025-2026

NOTE GIẢI ĐỀ HSG THPT TỈNH Tỉnh: Khánh Hòa Ngày thi: 22/01/2026
Người note: Mochi Kasato Link đề thi:
https://drive.google.com/file/d/1KZOjKAIMcvJphKE0xCfWNSmBKNAKumC 2/view?usp=sharing Link contest:
https://codeforces.com/contestInvitation/ec0a617522608015d3e0279c4d83694e
0e252a9a?fbclid=IwZXh0bgNhZW0CMTAAYnJpZBExWVVCMk5BRzhQN1Q5ND
BHWHNydGMGYXBwX2lkEDIyMjAzOTE3ODgyMDA4OTIAAR5X-
pgjSFAFmNQIPnZ5kREyxc_WgwLyQ58moS2E1_LDvM8rgGT8L3PwuZf9Ww_ae
m_EeaTIerH9hQ5-2NIC2pKVQ (contest từ anh Võ Văn Việt – Trường THPT Chuyên
Lê Quý Đôn – Đông Hải)
Video hướng dẫn giải tham khảo từ bên khác:
https://www.facebook.com/share/v/1AXhaBjpip/
(lấy từ page 11 Tin - Tổ chức hacker Đôn Lê đến từ Trường THPT Chuyên Lê Quý Đôn – Khánh Hòa!!)
Nhận xét đề này: Đề khá khó, subtask nhỏ cũng cho điểm hehe, có 1 bài lấy từ COCI…
Sắp xếp bài toán theo độ khó tăng dần:
Bài 1 → Bài 4 → Bài 2 → Bài 3
Bài 1: cau1 – Tổng phân số (5 điểm)
Link nộp bài: (chấm bài trong contest, link để ở trang đầu)
Lời giải tham khảo: Xem trong video tham khảo ở trang đầu. Nhận xét:
“Bài này có độ khó bằng với một bài trong sách SGK Tin trên trường” – theo lời kể của
một bạn nào đó trong phòng thi=)
Với bài này, ta chỉ cần tính tổng phân số như thường thôi. 1
Facebook: https://www.facebook.com/mochikasato/
Gọi kết quả phân số là 𝑡𝑢 . Khi này ta có: 𝑚𝑎𝑢 𝑡𝑢 𝑥 𝑥 𝑥
= 1 + 2 = 1 ∗ 𝑦2 + 𝑥2 ∗ 𝑦1 𝑚𝑎𝑢 𝑦1 𝑦2 𝑦1 ∗ 𝑦2
Để tối giản phân số trên, ta chỉ cần chia cả tử với mẫu cho “ước chung lớn nhất” của 2 số đó. Cụ thể: 𝑡𝑢 𝑡𝑢 gcd(𝑡𝑢, 𝑚𝑎𝑢) = 𝑚𝑎𝑢 𝑚𝑎𝑢 gcd(𝑡𝑢, 𝑚𝑎𝑢)
Độ phức tạp: 𝑂(1).
Code tham khảo: https://ideone.com/QPGwRA
// // Mochi Kasato - MKasato
// FB: https://www.facebook.com/mochikasato/ #include
#define boostcode ios_base::sync_with_stdio(0); cin.tie(0);
#define openf if (fopen("test.inp", "r")) {freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);} #define fi first #define se second #define pb(x) push_back(x) using namespace std; typedef long long ll; typedef pair pii; #define y1 ymot int x1, y1, x2, y2; int main() { boostcode; // openf;
cin >> x1 >> y1 >> x2 >> y2; ll mau = (ll)y1*y2;
ll tu = (ll)x1*y2 + (ll)x2*y1; ll ucln = __gcd(tu, mau); tu /= ucln; mau /= ucln;
cout << tu << ' ' << mau; return 0; } 2
Facebook: https://www.facebook.com/mochikasato/ /* TESTS: Test 1: 7 10 1 6 --> 13 15*/ 3
Facebook: https://www.facebook.com/mochikasato/
Bài 2: cau2 – Dãy tăng liên tiếp (5 điểm)
Link nộp bài: (chấm bài trong contest, link để ở trang đầu)
Lời giải tham khảo: Xem trong video tham khảo ở trang đầu. Nhận xét: Subtask 1:
Với subtask này, ta chỉ có 2 phần tử (𝑛 = 2).
Không mất tính tổng quát, giả sử 𝑎1 ≤ 𝑎2. Khi này, cách tối ưu nhất đó là giảm 𝑎2 xuống thành 𝑎′ ′
2 = 𝑎1 + 1 hoặc tăng 𝑎1 lên thành 𝑎1 = 𝑎2 − 1. Chọn 1 trong 2 cách này đều
mất 𝑎2 − 𝑎1 − 1 thao tác (ít thao tác nhất). Độ phức tạp: 𝑂(1). Subtask 2:
Với subtask này, ta thay đổi phát biểu bài toán thành như sau:
“Cho dãy số 𝑎1, 𝑎2, … , 𝑎𝑁. Hãy tìm giá trị 𝑥 để biến đổi dãy ban đầu thành dãy cấp số
cộng có công sai là 1, tức là 𝑎′ ′ ′ ′
1, 𝑎1 + 1, … , 𝑎1 + 𝑁 − 1 với 𝑎1 = 𝑥 sao cho số lượng thao
tác cần để biến đổi là nhỏ nhất.”
Khi này, ta cần tìm giá trị 𝑥 để 𝑛
∑|𝑎𝑖 − (𝑥 + 𝑖 − 1)| 𝑖=1 Là nhỏ nhất. (|𝑎 ′
𝑖 − (𝑥 + 𝑖 − 1)| là số lượng thao tác để biến đổi từ 𝑎𝑖 thành 𝑎1 + 𝑖 − 1).
Đặt 𝑏𝑖 = 𝑎𝑖 − 𝑖 + 1. Khi đó, biểu thức ở trên trở thành 𝑛 ∑|𝑏𝑖 − 𝑥| 𝑖=1 Hay 𝑛 ∑|𝑥 − 𝑏𝑖| 𝑖=1 (do |𝐴| = |−𝐴|). 4
Facebook: https://www.facebook.com/mochikasato/
Bài toán đã trở thành dạng bài quen thuộc “Tìm 𝑥 để tổng độ lệch |𝑥 − 𝑏𝑖| là nhỏ nhất”
(dạng bài này từng được nhắc đến trong “SGK Chuyên Tin – Tập 1” ở trang 45, trong
cuốn “Guide to Competitive Programming” của Antti Laaksonen ở mục “8.8.3.
Minimizing sums”, cũng như trong chuyên đề dạng bài “Tìm giá trị nhỏ nhất” của
chương trình Toán THCS). Ta chọn 𝒙 = trung vị của dãy 𝒃𝟏, 𝒃𝟐, … , 𝒃𝑵 thì tổng độ
lệch sẽ có giá trị là nhỏ nhất.
Để chứng minh cho tính chất ở trên:
• Giả sử ta cần tính giá trị nhỏ nhất của |𝑥 − 𝑎| + |𝑥 − 𝑏|. Ta có giá trị nhỏ nhất
của biểu thức là |𝑏 − 𝑎| (𝑏 − 𝑎 khi 𝑎 ≤ 𝑏, 𝑎 − 𝑏 khi 𝑎 ≥ 𝑏) khi 𝑥 ∈ [𝑎, 𝑏].
• Giờ quay lại bài toán gốc, với |𝑥 − 𝑏1|, |𝑥 − 𝑏2|, … , |𝑥 − 𝑏𝑁|, ta có thể tối ưu giá
trị biểu thức bằng cách ghép các cặp gồm số hạng trái cùng và phải cùng:
(|𝑥 − 𝑏1|, |𝑥 − 𝑏𝑁|) + (|𝑥 − 𝑏2|, |𝑥 − 𝑏𝑁−1|), …
Để biểu thức trên mang giá trị nhỏ nhất, ta chọn 𝑥 ∈ [𝑏1, 𝑏𝑁] ∩ [𝑏2, 𝑏𝑁−1] ∩ … 𝑥
sẽ là giao của khoảng các cặp được ghép, và giao điểm của các khoảng chính là
trung vị của dãy số 𝑏1, 𝑏2, … , 𝑏𝑁.
Có nhiều cách khác để chứng minh tính chất này, bạn nào muốn tìm hiểu hơn thì xem ở những link bên dưới:
• Bài viết cộng đồng thảo luận về cách chứng minh:
https://math.stackexchange.com/questions/113270/the-median-minimizes-the-
sum-of-absolute-deviations-the-ell-1-norm
• Bài viết chứng minh trong tập “The American Statistician” Vol. 44, năm 1990:
https://tommasorigon.github.io/StatI/approfondimenti/Schwertman1990.pdf
Sau khi tìm được 𝑥, ta chỉ cần tính 𝑛 ∑|𝑥 − 𝑏𝑖| 𝑖=1
Và in ra giá trị của biểu thức đó.
Độ phức tạp: 𝑂(𝑁 log 𝑁) (sort lại dãy ban đầu đê lấy trung vị, mất 𝑂(𝑁 log 𝑁)). 5
Facebook: https://www.facebook.com/mochikasato/
…Ta còn có nhiều cách khác để giải bài này, do biểu thức 𝑛 ∑|𝑥 − 𝑏𝑖| 𝑖=1
Là biểu thức của một hàm lồi, nên đồ thị hàm số sẽ là một đường cong có điểm cực
tiểu, thành ra ta giải bằng cách khác như chặt tam phân, chặt nhị phân cũng được.
Có thể tìm hiểu cách này trong video tham khảo để ở trang đầu. Code tham khảo: // Mochi Kasato - MKasato
// FB: https://www.facebook.com/mochikasato/ #include
#define boostcode ios_base::sync_with_stdio(0); cin.tie(0);
#define openf if (fopen("test.inp", "r")) {freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);} #define fi first #define se second #define pb(x) push_back(x) using namespace std; typedef long long ll; typedef pair pii; int n; int a[2002];
int b[2002]; // b[i] = a[i] - i + 1
int b2[2002]; // Là b[] nhưng được sắp xếp tăng dần int main() { boostcode; // openf; cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) b[i] = b2[i] = a[i]-i+1; sort(b2+1, b2+n+1);
int x = b2[(n+1)/2]; // x = trung vị của dãy b_1, b_2,..., b_N (được sắp xếp tăng dần) ll res = 0;
for (int i = 1; i <= n; i++) { res += abs(x - b[i]); } cout << res; 6
Facebook: https://www.facebook.com/mochikasato/ return 0; } /* TESTS: Test 1: 5 8 3 7 9 3 --> 13 */ 7
Facebook: https://www.facebook.com/mochikasato/
Bài 3: cau3 – Chia phần (5 điểm)
Nguồn bài: COCI ’16 Contest 4 #3 Kas (https://dmoj.ca/problem/coci16c4p3)
Lời giải tham khảo: https://dmoj.ca/problem/coci16c4p3/editorial hoặc xem trong
video tham khảo ở trang đầu.
Gợi ý trước khi đọc hướng dẫn cho subtask 2, 3: Đọc kỹ dữ kiện đề bài, cụ thể: “∑n c i=1 i ≤ 105”. Nhận xét:
Trước khi giải, ta quy ước 𝑆 là tổng giá trị của 𝑛 đồ vật đã cho (𝑆 = 𝑐1 + 𝑐2 + ⋯ . +𝑐𝑛),
𝑇 là tổng giá trị mỗi bên nhận được sau chi khia vật dụng (chưa tính thêm giá trị phiếu
mua hàng vào). Còn 𝑟𝑒𝑠 là kết quả bài toán cần tìm.
Vì ta cần tìm cách chia vật dụng với tổng giá trị cuối cùng của mỗi bên là lớn nhất, nên ta có:
𝑟𝑒𝑠 = min(𝑇 + (𝑆 − 𝑇 ∗ 2)) Hay
𝑟𝑒𝑠 = min(𝑆 − 𝑇)
Vậy bây giờ ta chỉ cần tìm cách chọn để 𝑇 lớn nhất là được. Subtask 1:
Trong subtask này, 𝑛 nhỏ (𝑛 ≤ 13) nên ta quy ước trạng thái 𝑏𝑖 cho vật dụng thứ 𝑖 như sau:
• Nếu chia cho bạn Nam: 𝑏𝑖 = 1.
• Nếu chia cho bạn Việt: 𝑏𝑖 = 2.
• Nếu không chia cho bạn nào: 𝑏𝑖 = 0.
Vì 𝑏𝑖 chỉ nhận vào 3 giá trị (0, 1 hoặc 2) nên ta có thể sinh từng dãy trạng thái
𝑏1, 𝑏2, … , 𝑏𝑛 có thể. Với mỗi dãy sinh được, ta tính 𝑇, kiểm tra nếu tổng giá trị chia cho
bạn Nam và Việt là như nhau, rồi cập nhật tổng giá trị mỗi người nhận được trong cách
chia đó (= 𝑆 − 𝑇) vào 𝑟𝑒𝑠 (nếu 𝑆 − 𝑇 < 𝑟𝑒𝑠).
Ta có thể sinh từng dãy trạng thái bằng quay lui hoặc sinh tam phân.
Độ phức tạp: 𝑂(3𝑛). 8
Facebook: https://www.facebook.com/mochikasato/ Subtask 2:
Từ cách quy ước trạng thái 𝑏𝑖 trong subtask 1, ta có thể nghĩ đến việc tính đến 𝑟𝑒𝑠 khi
chỉ xét đến 𝑖 vật dụng đầu, mà để vậy thì ta phải tính trước cách chọn tối ưu của các vật
dụng trước đó. Đều này dẫn đến phương pháp quy hoạch động như sau:
• Gọi 𝑓(𝑖, 𝑠1, 𝑠2) là trạng thái khi chỉ xét đến 𝑖 vật dụng đầu, với tổng giá trị chia
cho bạn Nam là 𝑠1, cho bạn Việt là 𝑠2 (0 ≤ 𝑠1, 𝑠2; 𝑠1 + 𝑠2 ≤ 𝑆). Ta quy ước
𝑓(𝑖, 𝑠1, 𝑠2) = 1 nếu chia được, còn 𝑓(𝑖, 𝑠1, 𝑠2) = 0 thì không chia được.
• Ta có công thức sau khi xét đến vật dụng thứ 𝑖:
𝑑𝑝(𝑖 − 1, 𝑠1, 𝑠2), 𝑑𝑝(𝑖, 𝑠 𝑑𝑝(𝑖 − 1, (𝑠 1, 𝑠2) = max ( 1 − 𝑐𝑖), 𝑠2),)
𝑑𝑝(𝑖 − 1, 𝑠1, (𝑠2 − 𝑐𝑖)) Với
o 𝑑𝑝(𝑖, 𝑠1, 𝑠2) = 𝑑𝑝(𝑖 − 1, 𝑠1, 𝑠2)
nếu không chia cho bạn nào.
o 𝑑𝑝(𝑖, 𝑠1, 𝑠2) = 𝑑𝑝(𝑖 − 1, (𝑠1 − 𝑐𝑖), 𝑠2) nếu chia cho bạn Nam.
o 𝑑𝑝(𝑖, 𝑠1, 𝑠2) = 𝑑𝑝(𝑖 − 1, 𝑠1, (𝑠2 − 𝑐𝑖)) nếu chia cho bạn Việt.
Ta có thể duyệt và tính mọi trạng thái 𝑑𝑝(𝑖, 𝑠1, 𝑠2) với 1 ≤ 𝑖 ≤ 𝑛, 𝑠1 + 𝑠2 ≤ 𝑆, xử lí tổng cộng 𝑆∗(𝑆+1) 𝑛 ∗ trạng thái. 2
Cuối cùng, ta sẽ có 𝑇 = 𝑠 với 𝑠 (1 ≤ 𝑠 ≤ 𝑆) là giá trị lớn nhất có trạng thái 𝑑𝑝(𝑛, 𝑠, 𝑠) =
𝑡𝑟𝑢𝑒. Từ đó ta tính được kết quả bài toán cần tìm: 𝑟𝑒𝑠 = 𝑆 − 𝑇 Độ phức tạp: 𝑆∗(𝑆+1) 𝑂 (𝑛 ∗
) ≈ 𝑂(𝑛 ∗ 𝑆2) (là số trạng thái cần xử lí quy hoạch động). 2 Subtask 3:
Tương tự subtask 2, vì ta chỉ quan tâm đến cách chia vật dụng sao cho tổng giá trị vật
dụng chia cho 2 bên là như nhau (theo yêu cầu đề bài), hay nói cách khác 𝑠1 = 𝑠2, nên
ta định nghĩa lại hàm xử lí quy hoạch động như sau:
• Không mất tính tổng quát, giả sử 𝑠1 ≤ 𝑠2.
• Gọi 𝑑𝑝(𝑖, 𝑥) là tổng giá trị vật dụng lớn nhất chia được cho mỗi bên, với 𝑥 là “độ
lệch” (hiệu tuyệt đối) của 𝑠1 và 𝑠2 (hay 𝑥 = |𝑠1 − 𝑠2| = 𝑠2 − 𝑠1). 9
Facebook: https://www.facebook.com/mochikasato/
• Ta có công thức sau khi xét đến vật dụng thứ 𝑖 (đảm bảo tồn tại cách chia thì mới
xét đến công thức bên dưới):
o Nếu không chia cho bạn nào:
𝑑𝑝(𝑖 + 1, 𝑥) = 𝑑𝑝(𝑖, 𝑥)
o Nếu chia cho 𝑠1 (bên có tổng giá trị nhỏ hơn):
𝑑𝑝(𝑖 + 1, |𝑥 − 𝑐𝑖|) = 𝑑𝑝(𝑖, 𝑥) + 𝑎𝑖
▪ Nếu 𝑠1 + 𝑐𝑖 > 𝑠2: 𝑥′ = |(𝑠1 + 𝑐𝑖) − 𝑠2| = 𝑠1 + 𝑐𝑖 − 𝑠2 = 𝑐𝑖 − 𝑥.
▪ Nếu 𝑠1 + 𝑐𝑖 ≤ 𝑠2: 𝑥 = |(𝑠1 + 𝑐𝑖) − 𝑠2| = 𝑠2 − 𝑠1 − 𝑐𝑖 = 𝑥 − 𝑐𝑖.
⇒ 𝑥′ = |𝑥 − 𝑐𝑖|.
o Nếu chia cho 𝑠2 (bên có tổng giá trị lớn hơn):
𝑑𝑝(𝑖 + 1, 𝑥 + 𝑐𝑖) = 𝑑𝑝(𝑖, 𝑥) + 𝑎𝑖
▪ 𝑥′ = |𝑠1 − (𝑠2 + 𝑐𝑖)| = 𝑠2 + 𝑐𝑖 − 𝑠1 = 𝑥 + 𝑐𝑖.
Vì “độ lệch” của 𝑠1 và 𝑠2 không quá 𝑆, hay 𝑥 ≤ 𝑆. Vậy nên ta xử lí quy hoạch động với
tổng cộng 𝑛 ∗ 𝑆 trạng thái thôi.
Cuối cùng, ta có 𝑟𝑒𝑠 = 𝑑𝑝(𝑛, 0) là kết quả bài toán cần tìm.
Độ phức tạp: 𝑂(𝑛 ∗ 𝑆) (là số trạng thái cần xử lí quy hoạch động).
Code tham khảo: https://ideone.com/m55dYG
// // Mochi Kasato - MKasato
// FB: facebook.com/mochikasato/
// Problem link: https://dmoj.ca/problem/coci16c4p3 #include
#define boostcode ios_base::sync_with_stdio(0); cin.tie(0);
#define openf if (fopen("test.inp", "r")) {freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);} #define fi first #define se second #define pb(x) push_back(x) using namespace std; typedef long long ll; typedef pair pii; int n; int c[502]; 10
Facebook: https://www.facebook.com/mochikasato/
int dp[200002]; // dp[x]: Trạng thái cho biết tồn tại cách chia i vật dụng đầu
int dp2[200002]; // Tương tự dp[x], nhưng dùng để xử lí với cách chia i+1 vật dụng đầu int main() { boostcode; // openf; cin >> n;
for (int i = 1; i <= n; i++) cin >> c[i];
// Tính S = c[1] + c[2] + ... + c[n]: int S = 0;
for (int i = 1; i <= n; i++) S += c[i];
// Xử lí quy hoạch động:
for (int x = 1; x <= S; x++) dp[x] = -1; // Ban đầu, để dp[x] = -1,
ngoại trừ dp[0] (do ban đầu không lấy vật nào hết)
for (int i = 1; i <= n; i++) {
for (int x = 0; x <= S; x++) dp2[x] = -1;
for (int x = 0; x <= S; x++) { if (dp[x] == -1) continue;
dp2[x] = max(dp2[x], dp[x]); // Không chia cho ai hết
dp2[abs(x-c[i])] = max(dp2[abs(x-c[i])], dp[x] + c[i]); // Chia
cho bạn có phần nhỏ hơn
dp2[x+c[i]] = max(dp2[x+c[i]], dp[x] + c[i]); // Chia cho bạn có phần lớn hơn }
for (int x = 0; x <= S; x++) dp[x] = dp2[x]; // lưu giá trị dp2[]
và reset lại dp2[] cho những lần xử lí dp với i kế tiếp }
// Tính kết quả bài toán cần tìm: int T = (dp[0])/2; int res = S - T; cout << res; return 0; } /* TESTS: Test 1: 5 2 3 5 8 13 --> 18 */ 11
Facebook: https://www.facebook.com/mochikasato/
Bài 4: cau4 – Mảnh đất trồng cây (5 điểm)
Lời giải tham khảo: Xem trong video tham khảo ở trang đầu. Nhận xét:
Ta gọi bảng các ô của khu vườn là ma trận 𝐴, kích thước 𝑛 × 𝑛. Subtask 1:
Với subtask này, 𝑛 = 2 nên ta có bảng như bên phải: 1 2 3 4
Khi này ta cứ if-else cho 4 trường hợp truy vấn của 4 ô đó.
Độ phức tạp: 𝑂(1). Subtask 2 + 3:
Với 2 subtask này, vì 𝑛 nhỏ (𝑛 ≤ 1000) nên ta có thể khởi tạo các giá trị trực tiếp cho ma trận 𝐴.
Trước tiên, ta khai báo mảng 𝐵 để sau đó lưu 𝐵𝑐 = (𝑥, 𝑦) (ở ô (𝑥, 𝑦) trồng loại cây 𝑐).
Ta gọi 𝑑𝑖𝑒𝑛(𝑥1, 𝑦1, 𝑥2, 𝑦2, 𝑙, 𝑟) là hàm đệ quy khởi tạo giá trị cho các ô thuộc vùng hình
vuông có chỉ số hàng/cột của 2 góc trái-trên và phải-dưới là (𝑥1, 𝑦1) và (𝑥2, 𝑦2), với giá
trị để điền vào các ô là các số 𝑙, 𝑙 + 1, … , 𝑟.
• Nếu 𝑙 ≤ 𝑟 thì gọi tiếp 4 hàm con để khởi tạo cho 4 phần chia nhỏ của bảng đang xét, với 𝑟−𝑙+1 𝑙𝑒𝑛 =
là số lượng con số được chia đều cho mỗi phần, 𝑚𝑖𝑑 4 𝑥 =
𝑥1 + 𝑥2, 𝑚𝑖𝑑𝑦 = 𝑦1 + 𝑦2: 𝑚𝑖𝑑 o 𝑚𝑖𝑑 𝑑𝑖𝑒𝑛 (𝑥 𝑥−1 𝑦−1 1, 𝑦1, ,
, 𝑙, 𝑙 + 𝑙𝑒𝑛 − 1): Khởi tạo cho phần 1. 2 2 𝑚𝑖𝑑 o 𝑚𝑖𝑑 𝑑𝑖𝑒𝑛 (𝑥 𝑦+1 𝑥−1 1, , , 𝑦 2 2
2, 𝑙 + 𝑙𝑒𝑛, 𝑙 + 𝑙𝑒𝑛 ∗ 2 − 1): Cho phần 2. 𝑚𝑖𝑑 o 𝑚𝑖𝑑 𝑑𝑖𝑒𝑛 ( 𝑥+1 , 𝑦+1 , 𝑥 2 2
2, 𝑦2, 𝑙 + 𝑙𝑒𝑛 ∗ 2, 𝑙𝑒𝑛 + 𝑙𝑒𝑛 ∗ 3 − 1): Cho phần 3. 𝑚𝑖𝑑 o 𝑚𝑖𝑑 𝑑𝑖𝑒𝑛 ( 𝑥+1 , 𝑦
𝑦−1 , 𝑙 + 𝑙𝑒𝑛 ∗ 3, 𝑟): Khởi tạo cho phần 4. 2 1, 𝑥2, 2
• Nếu 𝑙 = 𝑟 thì nghĩa rằng ta đang xét đến vùng chứa 1 ô vuông, nên ta điền trực
tiếp giá trị vào ô đó (hay gán 𝐴𝑥 = 𝑙). Ta cũng lưu 𝐵 1,𝑦1
𝑙 = (𝑥1, 𝑦1) để trả lời truy vấn loại 1 trong 𝑂(1).
Để khởi tạo ma trận 𝐴, ta chỉ cần gọi 𝑑𝑖𝑒𝑛(1,1, 𝑛, 𝑛, 1, 𝑛2) rồi sau đó ta lấy giá trị trực
tiếp từ ma trận để trả lời cho các truy vấn.
Độ phức tạp: 𝑂(𝑁2) (khởi tạo ma trận 𝐴 và mảng 𝐵 mất 𝑂(𝑁2), trả lời các truy vấn trong 𝑂(1)). 12
Facebook: https://www.facebook.com/mochikasato/ Subtask 4:
Thay vì khởi tạo trước giá trị từng ô cho ma trận 𝐴 như trong subtask 1, 2, 3, ta sẽ trực
tiếp tính kết quả cho từng truy vấn.
Về subtask 4: Với truy vấn loại 1 (1 𝑐):
• Ta xác định vùng mà chứa ô trồng cây loại 𝑐, xong rồi ta thu nhỏ phạm vi vùng
tìm kiếm và xác định tiếp vùng chứa ô trồng cây, thu nhỏ và tìm kiếm liên tục cho
đến khi vùng tìm kiếm chỉ còn 1 ô. Ô này chính là ô trồng cây loại 𝑐. • Cụ thể, gọi 𝑟−𝑙+1
𝑡𝑖𝑚(𝑥1, 𝑦1, 𝑥2, 𝑦2, 𝑙, 𝑟) (tương tự hàm 𝑑𝑖𝑒𝑛()) và 𝑙𝑒𝑛 = để xác 4
định chỉ số hàng/cột của ô trồng cây loại 𝑐, biết rằng ô đó thuộc vùng có chỉ số
hàng/cột 2 góc là (𝑥1, 𝑦1) và (𝑥2, 𝑦2) với giá trị các ô thuộc vùng đó là 𝑙, 𝑙 +
1, … , 𝑟. dựa vào tính chất ma trận theo đề bài cho, ta chia vùng tìm kiếm thành 4
vùng và xác định vùng con chứa ô trồng cây loại 𝑐 như sau:
Nếu 𝑙 ≤ 𝑐 ≤ 𝑙 + 𝑙𝑒𝑛 − 1: Thu nhỏ phạm vi về vùng của phần 1, gọi tiếp hàm 𝑚𝑖𝑑 𝑚𝑖𝑑 𝑡𝑖𝑚 𝑦 − 1 (𝑥 𝑥 − 1 1, 𝑦1, ,
, 𝑙, 𝑙 + 𝑙𝑒𝑛 − 1) 2 2
o Nếu 𝑙 + 𝑙𝑒𝑛 ≤ 𝑐 ≤ 𝑙 + 𝑙𝑒𝑛 ∗ 2 − 1: Thu nhỏ phạm vi về vùng của phần 2, gọi tiếp hàm 𝑚𝑖𝑑 𝑚𝑖𝑑 𝑡𝑖𝑚 𝑦 + 1 (𝑥 𝑥 − 1 1, , , 𝑦 2 2
2, 𝑙 + 𝑙𝑒𝑛, 𝑙 + 𝑙𝑒𝑛 ∗ 2 − 1)
o Nếu 𝑙 + 𝑙𝑒𝑛 ∗ 2 ≤ 𝑐 ≤ 𝑙 + 𝑙𝑒𝑛 ∗ 3 − 1: Thu nhỏ phạm vi về vùng của phần 3, gọi tiếp hàm 𝑚𝑖𝑑 𝑚𝑖𝑑 𝑡𝑖𝑚 𝑦 + 1 ( 𝑥 + 1 , , 𝑥 2 2
2, 𝑦2, 𝑙 + 𝑙𝑒𝑛 ∗ 2, 𝑙𝑒𝑛 + 𝑙𝑒𝑛 ∗ 3 − 1)
o Nếu 𝑙 + 𝑙𝑒𝑛 ∗ 3 ≤ 𝑐 ≤ 𝑟: Thu nhỏ phạm vi về vùng của phần 4, gọi tiếp hàm 𝑚𝑖𝑑 𝑚𝑖𝑑 𝑡𝑖𝑚 𝑦 − 1 ( 𝑥 + 1 , 𝑦
, 𝑙 + 𝑙𝑒𝑛 ∗ 3, 𝑟) 2 1, 𝑥2, 2
• Khi gọi đến hàm có 𝑙 = 𝑟, phạm vi tìm kiếm thu về còn 1 ô. Ta in ra 2 tham số 𝑥1
và 𝑦1 (hoặc 𝑥2 và 𝑦2) từ hàm gọi làm kết quả của truy vấn loại 1. 13
Facebook: https://www.facebook.com/mochikasato/
Về subtask 5: Với truy vấn loại 2 (2 𝑥 𝑦):
• Tương tự với truy vấn loại 1, ta khai báo hàm đệ quy 𝑙𝑜𝑎𝑖𝑐𝑎𝑦(𝑥1, 𝑦1, 𝑥2, 𝑦2, 𝑙, 𝑟)
để xác định vùng con chứa loại cây được trồng ở ô (𝑥, 𝑦), xong rồi ta thu nhỏ
phạm vi vùng tìm kiếm và xác định tiếp loại cây thuộc vùng nào, thu nhỏ và tìm
kiếm liên tục cho đến khi vùng tìm kiếm chỉ còn 1 ô. Khi đó ta có được giá trị
trong hàm đệ quy là tham số 𝑙 (hoặc 𝑟).
• Cách thực hiện hàm 𝑙𝑜𝑎𝑖𝑐𝑎𝑦() cũng tương tự với 𝑡𝑖𝑚(), chỉ khác ở điều kiện xác
định vùng con chứa loại cây cần tìm (xác định dựa vào 𝑥, 𝑦 thay vì 𝑐). Phần này
bạn đọc tự triển khai như ở subtask 5 (có thể xem code bên dưới để tham khảo).
Cuối cùng, về subtask 6: Ta kết hợp việc sử dụng 2 hàm 𝑡𝑖𝑚() và 𝑙𝑜𝑎𝑖𝑐𝑎𝑦() để trả lời
cho 2 loại truy vấn đề cho. Nếu giải được subtask 4, 5 thì nghĩa rằng bạn đã giải được subtask 6 rồi!
Độ phức tạp: 𝑂(𝑄 ∗ log4 𝑁) (với mỗi truy vấn, thực hiện hàm 𝑡𝑖𝑚() hoặc 𝑙𝑜𝑎𝑖𝑐𝑎𝑦()
trong 𝑂(log4 𝑁) vì cứ mỗi lần hàm gọi chính nó thì kích thước vùng tìm kiếm giảm đi
4 lần, mà kích thước vùng tìm kiếm ban đầu là 𝑁 × 𝑁 nên chỉ thu nhỏ phạm vi tìm kiếm
được tối đa log4 𝑁 lần).
Code tham khảo: https://ideone.com/9ShISu // Mochi Kasato - MKasato
// FB: facebook.com/mochikasato/ // Problem link: #include
#define boostcode ios_base::sync_with_stdio(0); cin.tie(0);
#define openf if (fopen("test.inp", "r")) {freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);} #define fi first #define se second #define pb(x) push_back(x) using namespace std; typedef long long ll; typedef pair pii; int n; int q; ll c; int x, y; 14
Facebook: https://www.facebook.com/mochikasato/
pair tim(int x1, int y1, int x2, int y2, ll l, ll r) { if (l == r) { return make_pair(x1, y1); } ll len = (r-l+1)/4; int midx = x1 + x2; int midy = y1 + y2;
if (l<=c && c<=l+len-1) return tim(x1, y1, (midx-1)/2, (midy-1)/2, l, l+len-1);
if (l+len<=c && c<=l+len*2-1) return tim(x1, (midy+1)/2, (midx-1)/2, y2, l+len, l+len*2-1);
if (l+len*2<=c && c<=l+len*3-1) return tim((midx+1)/2, (midy+1)/2, x2, y2, l+len*2, l+len*3-1);
if (l+len*3<=c && c<=r) return tim((midx+1)/2, y1, x2, (midy-1)/2, l+len*3, r); }
ll loaicay(int x1, int y1, int x2, int y2, ll l, ll r) {
if (x1==x2 && y1==y2) { return l; } ll len = (r-l+1)/4; int midx = x1 + x2; int midy = y1 + y2;
if (x1<=x && x<=(midx-1)/2 &&
y1<=y && y<=(midy-1)/2) return loaicay(x1, y1, (midx-1)/2, (midy- 1)/2, l, l+len-1);
if (x1<=x && x<=(midx-1)/2 &&
(midy+1)/2<=y && y<=y2) return loaicay(x1, (midy+1)/2, (midx-1)/2, y2, l+len, l+len*2-1);
if ((midx+1)/2<=x && x<=x2 &&
(midy+1)/2<=y && y<=y2) return loaicay((midx+1)/2, (midy+1)/2, x2, y2, l+len*2, l+len*3-1);
if ((midx+1)/2<=x && x<=x2 &&
y1<=y && y<=(midy-1)/2) return loaicay((midx+1)/2, y1, x2, (midy- 1)/2, l+len*3, r); } 15
Facebook: https://www.facebook.com/mochikasato/ int main() { boostcode; // openf; cin >> n; cin >> q; const ll N2 = (ll)n*n;
for (int i = 1; i <= q; i++) { int op; cin >> op; if (op == 1) { cin >> c;
pair res = tim(1, 1, n, n, 1, N2);
cout << res.fi << ' ' << res.se << '\n'; } else { // op == 2: cin >> x >> y;
cout << loaicay(1, 1, n, n, 1, N2) << '\n'; } } return 0; } /* TESTS: Test 1: 4 2 2 3 4 1 8 --> 10 2 3 Test 2: 8 4 1 4 2 3 4 1 15 2 5 7 --> 2 1 10 4 2 37 */ 16
Facebook: https://www.facebook.com/mochikasato/ HAVE A NICE DAY CODING!!! 17
Facebook: https://www.facebook.com/mochikasato/