Editorial for Coin
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.
Spoiler Alert
Hint 1
- Cách đơn giản nhất là duyệt qua từng đoạn \(1 \leq i \leq j \leq n\)
Gọi số lượng O trong đoạn là cntO
Gọi số lượng R trong đoạn là cntR
Chọn đoạn dài nhất thỏa cntO = cntR * k
Hint 2
- Dùng mảng cộng dồn ta có thể tính số lượng O, R trong \(O(1)\)
Gọi f(n, c) là số lượng kí tự c trong đoạn [1, n]
Có số lượng kí tự c trong đoạn [l, r] là f(r, c) - f(l - 1, c)
Hint 3
- Ta có thể tìm trước i một đoạn nào đó mà sau khi loại nó ra ta sẽ được kết quả cntO = cntR * k
Gọi cntO là số lượng kí tự O tính từ 1 -> i
Gọi cntR là số lượng kí tự R tính từ 1 -> i
Nếu cntO = cntR * k sẵn rồi thì cập nhật res = i
Nếu cntO - cntR * k tồn tại thì cập nhật res = max(res, vị trí hiện tại - vị trí cuối đoạn con đó)
Nếu cntO - cntR * k không tồn tại, thì ta đánh dấu vị trí cuối của nó là i
Reference AC code | O(n) time | O(1) auxiliary space | Online Solving, STL, Equalsum-problem ???
C++
int main()
{
int n, k;
cin >> n >> k;
char c;
while (c = getchar(), c != 'O' && c != 'R');
unordered_map<long long, int> M;
int res = 0;
int cntO = 0, cntR = 0;
for (int i = 1; i <= n; ++i, c = getchar())
{
(c == 'O') ? cntO++ : cntR++;
long long t = 1LL * cntO - 1LL * cntR * k;
if (t == 0) res = i;
if (M[t] != 0)
res = max(res, i - M[t]);
else
M[t] = i;
}
cout << res;
}
Comments