Hướng dẫn cho Dạ hội

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

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;
}

Bình luận

Không có bình luận nào.