Editorial for Dạ hội

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.

Spoiler Alert

Hint 1

  • Dãy có độ cồng kềnh nhỏ nhất là dãy có 1 phần tử

Hint 2

  • Cần đếm số dãy có độ cồng kềnh là 0

Hint 3

  • Cần đếm số dãy mà các phần tử là bằng nhau

Hint 4

  • Với mỗi dãy bằng nhau có độ dài \(n\) sẽ có \(\frac{n * (n + 1)}{2}\) cách chọn

Reference AC code | \(O(n)\) time | \(O(1)\) auxiliary space | Online Solving

C++
ll f(int x) { return 1LL * x * (x + 1) / 2; }
int main()
{
    int n = readInt();

    ll res = 0;
    int cnt = 0;
    for (int pre = 0, cur; n--; pre = cur)
    {
        cin >> cur;
        if (cur == pre) cnt++;
        else
        {
            res += f(cnt);
            cnt = 1;
        }
    }
    res += f(cnt);

    cout << res;
    return 0;
}

Comments

There are no comments at the moment.