Editorial for Bedao Mini Contest 22 - Đếm đi các bạn ơiiii
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors: ,
Subtask 1: ~n \le 1000~.
Duyệt mọi cặp số (~i~, ~j~) sao cho ~1 \le i < j \le n~. Nếu ~j - i > 5~ và ~|a_i - a_j|~ chia hết cho ~23~ thì tăng kết quả lên ~1~ đơn vị.
Subtask 2: ~n \le 2 \cdot 10^5~.
Nhận xét: ~|a_i - a_j|~ chia hết cho ~23~ khi và chỉ khi ~a_i \equiv a_j \pmod{23}~.
Ta lưu mảng ~cnt[x]~ với ý nghĩa là số lượng các số chia ~23~ dư ~x~.
Trong khi duyệt tới vị trí ~j~, mảng ~cnt[]~ cần lưu các số có vị trí ~i~ sao cho ~j - i > 5~. Khi vị trí ~j~ tăng dần, các số mà mảng ~cnt[]~ lưu sẽ tăng dần. Vì vậy, ta lưu một con trỏ là vị trí các phần tử đã được thêm vào mảng đếm ~cnt[]~.

Comments