let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2007 QBMSEQ - Dãy con không giảm dài nhất

solution.md

Công việc chính của bài này là kiểm tra xem một số có thuộc dãy \(u_k\) hay không, việc tìm dãy con dài nhất còn lại khá đơn giản. Có nhiều cách để kiểm tra một số có nằm trong dãy \(u_k\) hay không.

Cách thứ nhất, ta sinh dãy \(u_k\). Giới hạn số trong bài là \(10^8\) nên có khoảng \(10^4\) số cần sinh. Sau khi sinh ta có thể kiểm tra bằng tìm kiếm nhị phân hoặc cấu trúc Set/Bitset của STL.

Cách thứ 2, ta kiểm tra trực tiếp. Dễ thấy \(u_k\) là tổng các số nguyên từ 1 đến \(k\) nên:

\[u_k = \frac{k(k+1)}{2}\]

Để kiểm tra xem \(x\) có nằm trong \(u_k\) hay không, ta tìm \(k = \lfloor \sqrt{2x} \rfloor\) (\(\lfloor \rfloor\) là hàm làm tròn dưới), sau đó, \(x\) thuộc \(u_k\) nếu \(k(k+1)/2 = x\).

main.cpp
Open in Github Download
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

bool test(int a) {
    int k = sqrt(2*a);
    return k*(k+1) / 2 == a;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int &a: a) cin >> a;

    int l = 0, max_l = 0;
    for (int i=0; i<n; i++) {
        if (test(a[i])) {
            if (i>0 && a[i]>=a[i-1]) l += 1;
            else l = 1;
            max_l = max(max_l, l);
        } else l = 0;
    }

    cout << max_l;

    return 0;
}
Comments