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

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define vc vector<char>
#define pii pair<int, int>
#define pib pair<int, bool>
#define pdd pair<double, double>
#define mii map<int, int>
#define mib map<int, bool>
#define mil map<int, ll>
#define mli map<ll, int>
#define si set<int>
#define vvi vector<vi>
#define vvl vector<vl>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define yes cout << "YES\n";
#define no cout << "NO\n";
#define yn yes else no
#define ny no else yes

// #define int ll

#ifdef VanLam
#include <debug.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define cer(...) 20
#define debug(...) 12
#endif

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

int d;
vvi adj;
vi ind;
vb vis;

void dfs(int u)
{
    vis[u] = true;
    ind[u] = ++d;

    for (int v : adj[u])
    {
        if (!vis[v])
            dfs(v);
    }
}

void Van_Lam()
{
    int n, q;
    cin >> n >> q;
    adj.assign(n + 1, {});

    vi cnt(n + 1, 0);

    FOR(i, 0, n - 2)
    {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);

        cnt[u]++;
        cnt[v]++;
    }

    vis.assign(n + 1, false);
    ind.resize(n + 1);
    d = 0;
    FOR(i, 1, n)
    {
        if (cnt[i] == 1)
        {
            dfs(i);
            break;
        }
    }

    while (q--)
    {
        int u;
        cin >> u;
        if (!(ind[u] & 1) || (n - ind[u]) & 1) {
            cout << "Ron";
        } else {
            cout << "Hermione";
        }
    }
}

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

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    int t = 1;
    // cin >> t;
    int testcase = 1;
    while (t--)
    {
        cer("- - - -", testcase++, "- - - -");
        Van_Lam();
        cout << '\n';
        cer("= = = = = = = = = =");
    }
    return 0;
}

Link

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int, int>
#define mii map<int, int>
#define mib map<int, bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define lcm(a, b) a / gcd(a, b) * b

#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YesNo Yes else No
#define NoYes No else Yes

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

#ifdef VanLam
#include <VanLam.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define __gcd(a, b) gcd(a, b)
#else
#define cer(...) 20
#define debug(...) 12
#define gcd(a, b) __gcd(a, b)
#endif

// #define int ll

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

inline void prepare()
{
}

class Graph
{
public:
    int n;
    vvi adj;

    Graph(int n)
    {
        this->n = n;
        adj.assign(n + 1, vi());
    }

    void addEdge(int u, int v)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int dfs(int u, int par)
    {
        int res = 0;
        for (int v : adj[u])
        {
            if (v == par)
                continue;
            res |= (1 - dfs(v, u));
        }

        return res;
    }
};

inline void _VanLam_()
{
    int n, q;
    cin >> n >> q;

    Graph g(n);
    FOR(i, 1, n - 1)
    {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }

    int root;
    cin >> root;
    if (g.dfs(root, -1))
    {
        cout << "Ron\n";
    }
    else
    {
        cout << "Hermione\n";
    }
}

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

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    prepare();

    int Case = 1;
    // cin >> Case;
    while (Case--)
    {
        cer("- - - -", Case, "- - - -");
        _VanLam_();
        cer("= = = = = = = = = =");
    }

    return 0;
}

Link

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define ll long long
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>
#define pii pair<int, int>
#define mii map<int, int>
#define mib map<int, bool>
#define vvi vector<vi>
#define vvb vector<vb>
#define vvc vector<vc>
#define vpi vector<pii>
#define vvpi vector<vpi>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sub(x, l, r) (x).begin() + l, (x).begin() + r
#define rsub(x, l, r) (x).rbegin() + l, (x).rbegin() + r
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; i++)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; i--)

#define lcm(a, b) a / gcd(a, b) * b

#define Yes cout << "Yes\n";
#define No cout << "No\n";
#define YesNo Yes else No
#define NoYes No else Yes

template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

#ifdef VanLam
#include <VanLam.h>
#define cer(...) debug_out(__VA_ARGS__)
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define __gcd(a, b) gcd(a, b)
#else
#define cer(...) 20
#define debug(...) 12
#define gcd(a, b) __gcd(a, b)
#endif

// #define int ll

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

inline void prepare()
{
}

class Graph
{
public:
    int n;
    vvi adj;
    vi dp;

    Graph(int n)
    {
        this->n = n;
        adj.assign(n + 1, vi());
        dp.assign(n + 1, 0);
    }

    void addEdge(int u, int v)
    {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void dfs(int u, int par = -1)
    {
        for (int v : adj[u])
        {
            if (v == par)
                continue;
            dfs(v, u);
            dp[u] += (dp[v] == 0);
        }
    }

    void reRoot(int u, int par = -1)
    {
        if (par != -1)
        {
            dp[u] += (dp[par] == 0);
        }

        for (int v : adj[u])
        {
            if (v == par)
                continue;
            int tmp = (dp[v] == 0);

            dp[u] -= tmp;
            reRoot(v, u);
            dp[u] += tmp;
        }
    }
};

inline void _VanLam_()
{
    int n, q;
    cin >> n >> q;

    Graph g(n);
    FOR(i, 1, n - 1)
    {
        int u, v;
        cin >> u >> v;
        g.addEdge(u, v);
    }

    g.dfs(1, -1);
    debug(g.dp);
    g.reRoot(1, -1);
    while (q--)
    {
        int root;
        cin >> root;
        if (g.dp[root])
        {
            cout << "Ron\n";
        }
        else
        {
            cout << "Hermione\n";
        }
    }
}

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

    if (fopen("VanLam.inp", "r"))
    {
        freopen("VanLam.inp", "r", stdin);
        freopen("VanLam.out", "w", stdout);
    }

    prepare();

    int Case = 1;
    // cin >> Case;
    while (Case--)
    {
        cer("- - - -", Case, "- - - -");
        _VanLam_();
        cer("= = = = = = = = = =");
    }

    return 0;
}

Link

...

Link

...

Link

...