Hướng dẫn giải của Bedao Regular Contest 11 - SUPERQRY


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Đến với bài toán này, trước tiên ta sẽ tìm hiểu về cách tìm giá trị nhỏ nhất của một biểu thức:

Về mặt bài làm, khi chưa tìm ra được giá trị nhỏ nhất, các bạn sẽ không biết số đó là bao nhiêu. Nhưng trên thực tế, để "tìm" được giá trị nhỏ nhất, các bạn thường phải biết trước giá trị số đó trước khi biến đổi biểu thức.

Giả sử ta đã tìm ra được giá trị nhỏ nhất của ~A~ là ~v~, việc "tìm" giá trị nhỏ nhất của ~A~ sẽ qua hai bước

  • Bước 1: Sử dụng một số phương pháp toán học để chứng minh ~A \ge v~
  • Bước 2: Đưa ra một trường hợp xảy ra dấu bằng.

Chú ý; trong bài toán tìm giá trị nhỏ nhất, ta chỉ cần đưa ra một trường hợp dấu bằng xảy ra.

Quay trở lại bài toán, ta sẽ chứng minh ~max\{LIS(a), LDS(a)\} \ge \lceil \sqrt{n} \rceil~. Thật vậy:

Giả sử tồn tại một dãy ~a~ nào đó có ~LIS(a) < \lceil \sqrt{n} \rceil~ và ~LDS(a) < \lceil \sqrt{n} \rceil~.

Vì ~a~ có độ dài dãy con tăng dài nhất là ~LIS(a)~ nên có thể chia ~a~ thành ~LIS(a)~ dãy con giảm.

Mặt khác; theo nguyên lí Dirichlet, có ~n~ phần tử chia ra làm ~LIS(a)~ dãy con thì tồn tại ít nhất một dãy con có độ dài không bé hơn ~\frac{n}{LIS(a)} > \frac{n}{\lceil \sqrt{n} \rceil} \ge \lceil \sqrt{n} \rceil~. Tức là ~LDS(a) > \lceil \sqrt{n} \rceil~, trái với giả thiết.

Vậy giả thiết đặt ra là sai, ta thu được kết quả ~max\{LIS(a), LDS(a)\} \ge \lceil \sqrt{n} \rceil~

Dấu bằng xảy ra chẳng hạn khi:

~a = [n - \sqrt{n}, n - \sqrt{n} + 1, ..., n, \sqrt{n}, \sqrt{n} - 1, ..., 3, 2, 1, ...]~

Vậy, ~g(n) = \lceil \sqrt{n} \rceil~

Gọi ~f(n) = g(1) + g(2) + ... + g(n)~, đáp án bài toán của chúng ta là ~f(r) - f(l-1)~.

Để tính nhanh ~f(n)~; ta cần xem với mỗi số ~v~ từ 1 đến ~\lceil \sqrt{n} \rceil~, có bao nhiêu số ~x~ mà ~g(x) = v~:

  • Nếu ~v < \lceil \sqrt{n} \rceil~, sẽ có ~v^2 - (v-1)^2 = 2 \times v - 1~ số ~x~ có ~g(x) = v~
  • Nếu ~v = \lceil \sqrt{n} \rceil~, sẽ có ~n - (v-1)^2~ số ~x~ có ~g(x) = v~

Theo đó: ~f(n) = 1 \times (2 \times 1 -1) + 2 \times (2 \times 2 - 1) + ... + (\lceil \sqrt{n} \rceil - 1) \times [2 \times (\lceil \sqrt{n} \rceil - 1) - 1] + \{\lceil \sqrt{n} \rceil \times [n - (\lceil \sqrt{n} \rceil - 1) ^ 2]\}~

~f(n) = (2\times 1^2 - 1) + (2 \times 2^2 - 2) + ... + [2 \times (\lceil \sqrt{n} \rceil - 1) ^ 2 - (\lceil \sqrt{n} \rceil - 1)] + \{\lceil \sqrt{n} \rceil \times [n - (\lceil \sqrt{n} \rceil - 1) ^ 2]\}~

~f(n) = 2\times [1^2 + 2^2 + ... + (\lceil \sqrt{n} \rceil - 1) ^ 2] - [1 + 2 + ... + (\lceil \sqrt{n} \rceil - 1)] + \{\lceil \sqrt{n} \rceil \times [n - (\lceil \sqrt{n} \rceil - 1) ^ 2]\}~

~f(n) = 2\times \frac{(\lceil \sqrt{n} \rceil - 1) \times [(\lceil \sqrt{n} \rceil - 1) + 1] \times [2 \times (\lceil \sqrt{n} \rceil - 1) + 1]}{6} - \frac{(\lceil \sqrt{n} \rceil - 1) \times (\lceil \sqrt{n} \rceil) }{2} + \{\lceil \sqrt{n} \rceil \times [n - (\lceil \sqrt{n} \rceil - 1) ^ 2]\}~

~f(n) = \frac{\lceil \sqrt{n} \rceil \times (\lceil \sqrt{n} \rceil - 1) \times (2 \times \lceil \sqrt{n} \rceil - 1)}{3} - \frac{(\lceil \sqrt{n} \rceil - 1) \times (\lceil \sqrt{n} \rceil) }{2} + \{\lceil \sqrt{n} \rceil \times [n - (\lceil \sqrt{n} \rceil - 1) ^ 2]\}~

Đến đây, bài toán đã giải xong, quá là vật vã với một bài toán.

Code mẫu

#include <bits/stdc++.h>

#define fi first
#define se second
#define For(i, a, b) for (int i=a;i<=b;++i)
#define Ford(i, a, b) for(int i=a;i>=b;--i)

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef array<int, 3> arr;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = 2 * 1e5 + 5;
const int R = 1e9;

ll f[N];

void solve()
{
    for (int i = 1; i * i <= R; ++i) {
        ll cnt = i * i - (i - 1) * (i - 1);
        f[i] = f[i - 1] + cnt * i;
    }
    int q; cin >> q;
    while (q--) {
        ll l, r; cin >> l >> r;
        ll sl = sqrt(l), sr = sqrt(r);
        ll ans = 0;
        if (sl == sr) {
            ans = (r - l + 1) * (sl + 1);
            if (sl * sl == l) ans--;
        }
        else {
            if (sl * sl != l) {
                ans += ((sl + 1) * (sl + 1) - l + 1) * (sl + 1);
                sl++;
            }
            else ans += sl;
            ans += (r - sr * sr) * (sr + 1);
            if (sr > sl) ans += f[sr] - f[sl];
        }
        cout << ans << "\n";
    }
}

int main()
{
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    solve();

    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.