Giả sử, cố định vị trí $$$a_j$$$ thì bạn cần duyệt tất cả những vị trí $$$a_i$$$ $$$(1 \le i \le j \le n)$$$, rồi tính $$$max(a_i - a_j)$$$. Nhưng độ phức tạp thuật toán sẽ là $$$O(n^2)$$$, quá xấu với giới hạn của đề bài.

Để giảm thiểu độ phức tạp của thuật toán, với mỗi $$$a_j$$$, ta thấy $$$max(a_i - a_j) = max(a_i) - a_j$$$. Để nhanh chóng tìm được $$$max(a_i)$$$, bạn cần tính trước mảng pre, với $$$pre[i] = max(a_1, a_2, ..., a_i)$$$.

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 5;

int a[maxN], pre[maxN];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = max(pre[i - 1], a[i]);
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res = max(res, pre[i] - a[i]);
    }
    cout << res;
}

Ta thấy $$$abs(a_i - a_j) = abs(a_j - a_i)$$$, vì vậy thứ tự xuất hiện trong mảng không còn quan trọng.

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 5;
const int INF = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;

        int mx = -INF, mn = INF;
        for (int i = 1; i <= n; i++)
        {
            int a;
            cin >> a;
            mx = max(mx, a);
            mn = min(mn, a);
        }

        cout << mx - mn << "\n";
    }
}

Bài toán tương đương việc tìm hai vị trí $$$i$$$ và $$$j$$$ sao cho $$$(pre[j] - pre[i])$$$ $$$mod$$$ $$$k == 0$$$, $$$pre[i[$$$ được định nghĩa là tổng tiền tố từ $$$1$$$ đến $$$i$$$.

Dễ thấy để $$$(pre[i] - pre[j])$$$ $$$mod$$$ $$$k == 0$$$ thì $$$pre[i]$$$ và $$$pre[j]$$$ phải đồng dư khi chia dư cho $$$k$$$. Sử dụng map, với $$$mp[x]$$$ là vị trí đầu tiên bên trái $$$pre[i]$$$ $$$mod$$$ $$$k == x$$$.

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 5;
const int INF = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;

        map<int, int> first_index;
        first_index[0] = 0;

        int res = 0, tot = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            cin >> x;
            tot += x;
            tot %= k;

            if (first_index.find(tot) == first_index.end())
            {
                first_index[tot] = i;
            }
            else
            {
                res = max(res, i - first_index[tot]);
            }
        }

        cout << res << "\n";
    }
}

Dễ thấy, ta luôn có thể xoá được phần tử lớn nhất ra khỏi mảng nếu tồn tại ít nhất một phần tử bên trái và bên phải của nó. Vì vậy ta chỉ cần để hai phần tử nhỏ nhất ra hai đầu mút.

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 5;
const int INF = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;

        for (int i = 2; i <= n; i++)
            cout << i << " ";
        cout << 1 << "\n";
    }
}

Ta sử dụng DP, ta định nghĩa $$$dp[i][j]$$$ là số cách di chuyển tới ô $$$(i, j)$$$. Vì ta có thể đi tới ô $$$(i, j)$$$ bằng cách đi từ ô $$$(i - 1, j)$$$ hoặc ô $$$(i, j - 1)$$$, nên ta có công thức $$$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$$$ và $$$dp[1][1] = 1$$$

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e3 + 5;
const int MOD = 1e9 + 7;

int dp[maxN][maxN];

void prepare()
{
    dp[1][1] = 1;

    for (int i = 1; i < maxN; i++)
    {
        for (int j = 1; j < maxN; j++)
        {
            dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
            dp[i][j] %= MOD;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    prepare();

    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;

        cout << dp[n][m] << "\n";
    }
}

Nếu ta liệt kê lại các bước đi, ta sẽ thấy quãng đường đi gồm $$$n + m - 2$$$ bước, trong đó có $$$n - 1$$$ bước đi xuống dưới và $$$m - 1$$$ bước đi sang bên phải. Từ đó ta dễ dàng nhận thấy, số cách di chuyển là $$$C(n + m - 2, n - 1)$$$ cách.

#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e6 + 5;
const int MOD = 1e9 + 7;

#define int long long

int bPow(int n, int k, int mod = MOD)
{
    if (k == 0)
        return 1;

    int res = bPow(n, k >> 1, mod);
    res = res * res % mod;
    if (k & 1)
        res = res * n % mod;
    return res;
}

int fact[maxN], in_fact[maxN];

int C(int n, int k)
{
    if (k < 0 || k > n)
        return 0;

    return (fact[n] * in_fact[k] % MOD) * in_fact[n - k] % MOD;
}

void prepare()
{
    fact[0] = 1;
    for (int i = 1; i < maxN; i++)
    {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    in_fact[maxN - 1] = bPow(fact[maxN - 1], MOD - 2);
    for (int i = maxN - 2; i >= 0; i--)
    {
        in_fact[i] = (in_fact[i + 1] * (i + 1)) % MOD;
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    prepare();

    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        cout << C(n + m - 2, n - 1) << "\n";
    }
}

Giả sử đáp án chính là số nguyên dương thứ $$$k$$$ mà chúng ta cần "dịch sang phải" một số lần nào đó. Mỗi bội số của $$$n$$$ sẽ làm đáp án của chúng ta tăng thêm $$$1$$$. Số lượng những bội số như vậy là $$$\text{need} = \left\lfloor \frac{k - 1}{n - 1} \right\rfloor$$$. Vậy đáp án cuối cùng sẽ là $$$k + need$$$

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;

        int need = (k - 1) / (n - 1);
        cout << k + need << "\n";
    }
}

Ý tưởng chính

Trong nhiều bài toán dạng "đếm số lượng trên đoạn $$$[l, r]$$$", có một thủ thuật phổ biến là:

• Tính đáp án cho đoạn $$$[0, r]$$$,

• Sau đó trừ đi đáp án cho đoạn $$$[0, l − 1]$$$.

Chúng ta có thể áp dụng thủ thuật này trong bài toán như sau:

• Tính số cặp $$$(i, j)$$$ sao cho tổng của các phần tử còn lại nhỏ hơn $$$y + 1$$$,

• Sau đó trừ đi số cặp sao cho tổng nhỏ hơn $$$x$$$.

Bài toán con cần giải

Cho một mảng và một số nguyên $$$x$$$, hãy tính số cách chọn $$$(i, j)$$$ $$$(1 \le i \lt j \le n)$$$ sao cho tổng các phần tử còn lại (ngoài $$$a_i$$$ và $$$a_j$$$) nhỏ hơn $$$x$$$.

Phân tích độ phức tạp

Cách đơn giản (naive):

• Duyệt qua tất cả cặp $$$(i, j)$$$ và tính tổng phần còn lại.

• Độ phức tạp: $$$O(n^3)$$$.

Cải thiện đầu tiên:

• Nếu ta biết tổng $$$s$$$ của toàn bộ mảng, khi loại bỏ $$$a_i$$$ và $$$a_j$$$, tổng còn lại là $$$s − a_i − a_j$$$.

• Tính toán này chỉ mất $$$O(1)$$$, giảm xuống $$$O(n^2)$$$.

Nhưng $$$O(n^2)$$$ vẫn quá chậm. Ta cần nhanh hơn.

Ý tưởng tối ưu

• Nếu ta sắp xếp mảng, đáp án không thay đổi.

• Với mảng đã sắp xếp, cho một chỉ số $$$i$$$, tất cả các giá trị $$$j$$$ thỏa mãn điều kiện sẽ tạo thành một đoạn suffix liên tiếp.

(Nếu $$$s − a_i − a_j \lt x$$$ và $$$a_{j+1} ≥ a_j$$$, thì $$$s − a_i − a_{j+1} \lt x$$$).

• Sử dụng two pointer hoặc binary search để tìm kiếm

#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int n, x, y;
        cin >> n >> x >> y;

        vector<int> a(n);
        int tot = 0;

        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            tot += a[i];
        }
        sort(a.begin(), a.end());

        int mn = tot - y, mx = tot - x;

        int res = 0;
        for (int i = 0; i < n; i++)
        {
            int l = lower_bound(a.begin() + i + 1, a.end(), mn - a[i]) - a.begin();
            int r = upper_bound(a.begin() + i + 1, a.end(), mx - a[i]) - a.begin();

            res += (r - l);
        }

        cout << res << '\n';
    }
}

Link

Link

Link

Link

Link

Link