Bài  A: Bộ ba String.

Với mỗi i  (1 <= i <= n với n là độ dài của những string). Nếu c_i = a_i, có thể đổi chổ c_i cho b_i, hoặc nếu c_i = b_i, có thể đổi chổ ci cho ai, như vậy ta mới đc a_i = b_i. Vì vậy, chỉ cần kiểm tra xem c_i == a_i hoặc c_i == b_i, nếu điều kiện đúng với mọi i thì in YES, ngược lại in NO.

Độ phức tạp: O(n)

Bài B: Trò chơi TowerDiv. 

TH đặc biệt:

Đầu tiên, ta hãy xét 1 trường hợp đặc biệt, đó là trường hợp m=1, khi đó người chơi thứ nhất không thể tách bất cứ tòa tháp nào, vì vậy người thứ 2 sẽ thắng. 

N chẵn:

Nếu trong trường hợp số tháp (n) là chẵn, hãy tưởng tượng rằng ta sẽ chia những tòa tháp này thành 2 nhóm. Bởi vì ban đầu chiều cao của tất cả các tháp đều bằng nhau.

Vì vậy  khi người chơi thứ nhất thực hiện lượt chơi của mình ở 1 tòa tháp của 1 trong 2 nhóm bất kì, người chơi thứ 2 luôn luôn có thể bắt chước theo người chơi thứ nhất bằng cách chọn 1 tòa tháp có chiều cao giống hệt ở nhóm còn lại. 

Vì vậy người chơi thứ 2 sẽ luôn thực hiện được lượt chơi của mình => Người chơi thứ 2 sẽ thắng

N lẻ:

Trong trường hợp ngược lại n lẻ, người chơi thứ nhất có thể giảm chiều cao của tòa tháp bất kì thẳng xuống 1. và còn lại n-1 tòa tháp sẽ là số chẵn, và lúc này, người chơi thứ 2 sẽ đóng vai trò là người chơi thứ nhất trong bài toán N chẳn. Vì vậy người thứ 1 sẽ thắng.

Bài C : KID và sự phụ thuộc.

Mình rất xin lỗi các bạn vì đã ra bài này.

Tư tưởng : Dijkstra + đồng dư.

Xét đồ thị gồm m đỉnh là các số dư khi chia một số cho m, các đỉnh của đồ thị ứng với các số dư là 0, 1, 2,.. m-1. Lần lượt lấy số dư của phép chia ai cho m. Ta nhận thấy rằng, nếu ai  chia cho m dư x thì sẽ có các cạnh nối (0,x),(1,x+1),(2,x+2),.. với trọng số là ai. Với trường hợp ai < aj, mà ai và aj có cùng số dư khi chia cho m thì ta chỉ xét ai. Gọi d(i) là đường đi ngắn nhất từ đỉnh 0 đến i đỉnh còn lại( 1<= i <= m), đây cũng là tổng nhỏ nhất tạo được từ n số đã cho thỏa mãn điều kiện khi chia cho m có số dư là i. 

Vậy bi là số phụ thuộc nếu bi >= d(bi mod m).

Bài D: KID và lũ mèo.

-  Để dễ hình dung bài toán, ta đưa về dạng trục số, đánh dấu các khối lượng biết trước và nhãn S hay NS trên trục số, từ đó xem xem trên đoạn [a, b], các điểm có khoảng cách như thế nào đến các điểm được dán nhãn sẵn.

-  Đầu tiên, sắp xếp lại toàn bộ những con mèo theo khối lượng. Lưu ý thêm hai điểm dương vô cùng và âm vô cùng để có thể bao quát toàn bộ trục số, hai điểm này sẽ có nhãn là NS.

-  Xét trên 2 điểm liên tiếp trên trục số, S là điểm bắt đầu, E là điểm kết thúc, như vậy ta sẽ xét khoảng [S+1, E] (không xét điểm ngoài cùng bên phải, vì sẽ lặp lại khi ta xét điểm tiếp theo).

-  Đặt M = ( S+ E)/2. Những điểm bên trái [S+1, M] sẽ mang cùng nhãn với nhãn của điểm S, còn những điểm bên phải [M, E] sẽ mang cùng nhãn với điểm E. Tuy nhiên, bài toán giới hạn trong khoảng từ a đến b vì vậy, ta cần hiệu chỉnh lại một chút, những điểm cùng nhãn với S là [max(S+1, a), min(M, b)], còn những điểm cùng nhãn với điểm E là [max(M, a), min(E, b)]. Như vậy thì ta chỉ cần tính thêm những con có nhãn S là được. 

Số lượng số tự nhiên trong khoảng [x, y] là y-x+1, lưu ý thêm trường hợp tại M.

Bài E: Hải và nghiên cứu về Corona.

Với 1 số bất kì, ta luôn có thể phân tích chúng thành tổng của các số là lũy thừa của 2. Ví dụ dễ dàng thấy nhất là khi ta chuyển 1 số thành số nhị phân. Ví dụ như 13, khi được chuyển thành số nhị phân sẽ là 1101. Tương ứng với 13=1.2⁰+0.2¹+1.2²+1.2³

mà với cách phân tích này, dễ dàng nhận thấy rằng đây là cách phân tích có số lượng số hạng ít nhất. 

Vì vậy, nếu để phân tích 1 số ra được tổng của K số lũy thừa của 2. Thì số đó phải phân tích theo cách trên được số lượng số hạng nhỏ hơn K thì mới có thể phân tích thành k số hạng được. 

Khi đó, ta có thể dễ dàng tăng số lượng số hạng lên bằng cách thay 1 số hạng có mũ bậc x, thành 2 số hạng có mũ bậc x-1. Bởi vì:

2^x=2.2^x-1 

Ví dụ 1 số 2³, ta có thể thay thành 2 số 2² 

Ta có thể tăng số số hạng bằng cách trên cho đến khi đủ k số hạng thì dừng hoặc không còn số nào để tách được nữa. 

Bài F: Hai mảng đặc biệt.

Có thể biến đổi đề thành tìm một mảng như sau:

Đây là 1 mảng có độ dài 2m và phải được sắp xếp theo thứ tự không giảm, mà mỗi phần tử là 1 số nguyên từ 1 đến n.

Bài toán trở thành tìm số cách chọn ra 2m phần tử trong n số (từ 1 đến n), mỗi phần tử có thể lặp lại nhiều lần, và không tính đến thứ tự sắp xếp của chúng. Đây chính là tổ hợp lặp chập 2m của n phần tử.

Vậy kết quả là:

Vì n <= 1000 nên nếu tính công thức trên bình thường sẽ bị tràn số và phép chia không thể dùng đồng dư.

Có thể làm như sau:

• Gọi A là mảng các nhân tử ở tử số: A = {1, 2, …, n+2m-1}

• Gọi B là mảng các nhân tử ở mẫu số: B = {1, 2, …, 2m, 1, 2, …, n-1}

• Biết chắc chắc rằng chỉnh hợp cho ra kết quả nguyên, tức là tử số chia hết cho mẫu số, dùng 2 FOR lồng nhau để rút gọn tử số và mẫu số:

• Lúc này mẫu số đã rút gọn hết, chỉ cần tính tích các nhân tử ở tử số kết hợp đồng dư 10⁹+7.

Độ phức tạp: O((n+2m)²)