Hướng dẫn giải, Đề thi tuyển sinh lớp 10 chuyên Tin, trường Phổ Thông Năng Khiếu, năm học 2020 - 2021

Mời các bạn tham khảo
Hướng dẫn giải Đề thi tuyển sinh lớp 10 chuyên Tin trường Phổ Thông Năng Khiếu, năm học 2020 - 2021
Test chấm thử đã có. Các bạn liên hệ fb Coder Nhí để tạo tài khoản chấm thử nhé.
---

 Bài 1. PAIRLCM Cặp số

Xét 2 số nguyên dương a, b

Gọi u là ước chung lớn nhất của a, b : u = gcd(a, b)

Gọi k là bội chung nhỏ nhất của a, b : k = lcm(a,b ) = a * b / u

Nhắc lại bài toán ta cần tìm cặp số a, b sao cho lcm(a, b) max hay (a * b / u) max

Xét (a * b / u) max khi (a * b) max và u min. Trong đó U là ước chung lớn nhất của 2 số nguyên dương, nên giá trị min nhất chỉ có thể là 1, khi đó ta nói a, b là 2 số nguyên tố cùng nhau.

Bài toán quy thành : tìm 2 số a, b nguyên tố cùng nhau sao cho a + b = N và abs(a – b) là nhỏ nhất ( để a * b là lớn nhất )

Bài tương tự:

https://codeforces.com/contest/1372/problem/B?fbclid=IwAR3cVhbFMzTF-C0x5x60XbgWrdk6OeiYGwLQJY5ruYCJV4_hb6cIusLbHss

Bài 2. PAINTING Sơn hình vuông

xét thấy chỉ cần tìm xem vị trí mà ô đang xét là nằm ở hàng rìa thứ bao nhiêu, sau đó lấy vị trí hàng rìa vừa tìm được, mod cho 3 rồi sau đó in ra kết quả dựa trên phần dư.

Bài 3. PARENTHESES Dãy ngoặc

Nhận xét 1 : Sẽ không tồn tại một dãy ngoặc đúng nào nếu có số lượng dấu ngoặc mở không bằng số lượng dấu ngoặc đóng

Nhận xét 2: Nếu dãy ngoặc là cân bằng ( tức số lượng dấu ngoặc mở bằng số lượng dấu ngoặc đóng) thì luôn luông tồn tại ít nhất 1 cách để đua nó về dãy ngoặc đúng

Nhận xét 3: Ta sẽ lần lượt xét sự cân bằng của dãy ngoặc qua từng vị trí i ( i = 1.. n), ta sẽ từ trái sang phải, sự cân bằng ở đây là hiệu số giữa số lượng dấu ngoặc mở và số lượng dấu ngoặc đóng. Tính đến vị trí thứ i, gọi A[i] và B[i] lần lượt là số lượng dấu ngoặc mở và số lượng dấu ngoặc đóng, nếu a[i] – b[i] < 0, thì xâu tiền tố độ dài i không cân bằng, lúc này ta có 2 cách : 1 là đem vài dấu ngoặc đóng ở trước vị trí i ra đằng sau, 2 là đem vài dấu ngoặc mở ở sau vị trí i ra đằng trước, 2 cách này đều cho kết quả là như nhau.

NHƯ VẬY kết quả của bài toán là số lượng vị trí i sao cho A[i] – B[i] < 0

Bài tương tự: https://codeforces.com/contest/1374/problem/C?f0a28=1

Bài 4. MONITOR Hệ thống giám sát

*Cách 1: dùng mảng đánh dấu (vì giới hạn ai là 1018 nên dùng map trong c++ hoặc linked list)

*Cách 2: Tạo mảng n phần tử, mỗi phần tử sẽ lưu thời gian và id của người đến lúc ai. Sort mảng lại theo thứ tự id và thời gian tăng dần, duyệt từ 1 đến n, sử dụng 2 biến để lưu và tìm ra max thời gian đầu tiên và cuối cùng của một người