7

[Hướng dẫn giải đề thi] HSG TP HN - THPT - Vòng 1 - 2022

posted on Sept. 10, 2023, 3:00 p.m.

BÀI 1: SỐ CHÍNH PHƯƠNG ĐẶC BIỆT

1. Subtask 1

Với subtask này, có thể duyệt qua tất cả các số trong đoạn ~[a, b]~ và kiểm tra xem số đang xét có phải là số đặc biệt không.

Số ~x~ là số đặc biệt nếu thỏa mãn điều kiện sau:

  • ~x~ là số chính phương ~(1)~.
  • ~\sqrt{x}~ là số nguyên tố ~(2)~.

Điều kiện ~(1)~ có thể kiểm tra nếu ~\lfloor \sqrt{x} \rfloor \times \lfloor \sqrt{x} \rfloor = x~ thì ~x~ là số chính phương. (~\lfloor x \rfloor~ là số nguyên lớn nhất không vượt quá ~x~).

Điều kiện ~(2)~ có kiểm tra bằng cách duyệt ước trong đoạn ~[2..\sqrt{N}]~.

2. Subtask 2

Việc duyệt qua tất cả các số trong đoạn ~[a, b]~ ở subtask này là bất khả thi bởi ~a \le b \le 10^{12}~.

Ta có nhận xét: Từ ~1~ đến ~10^{12}~ chỉ có tối đa ~10^6~ số chính phương. Từ đó, chỉ cần duyệt qua các số trong đoạn ~[2..10^6]~ và kiểm tra xem số đang xét ~x~ có nguyên tố không. Nếu ~x~ là số nguyên tố thì ta kiểm tra nếu ~a \le x \times x \le b~ thì tăng ~ans~ lên ~1~ đơn vị.

Việc kiểm tra số nguyên tố có thể sử dụng Sàng Eratosthenes.

Code C++ tham khảo

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

int a, b;

namespace SUB1{
    bool scp(int x){
        return (int)sqrtl(x) * (int)sqrtl(x) == x;
    }
    void solve(){
        int ans = 0;
        for (int i = a; i <= b; i++){
            if (scp(i)){
                int x = sqrtl(i);
                bool check = true;
                for (int j = 2; j * j <= x; j++){
                    if (x % j == 0){
                        check = false;
                        break;
                    }
                }
                ans += check;
            }
        }
        cout << ans << endl;
    }
}

namespace SUB2{
    const int maxn = 1e6 + 5;
    bool isPrime[maxn];

    void sieve(){
        fill(isPrime + 2, isPrime + maxn, true);
        for (int i = 2; i < maxn; i++){
            if (isPrime[i]){
                for (int j = i * i; j < maxn; j += i){
                    isPrime[j] = false;
                }
            }
        }
    }

    bool inRange(int l, int r, int x){
        return l <= x && x <= r;
    }

    void solve(){
        sieve();
        int ans = 0;

        for (int i = 2; i <= 1000000; i++){
            if (isPrime[i] && inRange(a, b, i * i)){
                ans++;
            }
        }

        cout << ans << endl;
    }
}



void PROGRAM(int _){
    cin >> a >> b;
    if (b <= 1000000) SUB1::solve();
    else SUB2::solve();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;
    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

BÀI 2: BẢNG SỐ

Subtask 1

Với ~n \le 10^3~ thì bảng có tối đa ~n \times n \le 10^6~ phần tử. Từ đó, ta có thể dựng cả bảng mảng ~a~ có kích thước ~n \times n~ với ~a[i][j] = i \times j~. Duy trì một biến đếm ~ans~ lưu kết quả rồi duyệt qua mảng ~a~, nếu ~a[i][j] = x~ thì tăng ~ans~ lên ~1~ đơn vị.

Độ phức tạp: ~\mathcal{O}(n^2)~

Subtask 2

Bài toán có thể diễn giải lại như sau: tìm số cặp ~(i, j)~ thỏa mãn ~i \times j = x~ với ~1 \le i \le n, 1 \le j \le n~.

Từ đó, có thể duyệt qua tất cả các ước của ~x~ trong đoạn ~[1..\sqrt{x}]~. Nếu khi duyệt gặp ~u~ là ước của ~x~, gọi ~v = x / u~, ta cần kiểm tra xem nếu ~1 \le u \le n~ và ~1 \le v \le n~ thì tăng ~ans~ lên ~2~ đơn vị nếu ~u \neq v~ (tồn tại hai cặp ~(u, v)~ và ~(v, u)~), lên ~1~ đơn vị nếu ~u = v~.

Độ phức tạp: ~\mathcal{O}({\sqrt{x}})~.

Code C++ tham khảo

/*
Tag: 
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

int n, x;

namespace SUB1{
    const int maxn = 1e3 + 5;
    void solve(){
        int ans = 0;
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if (i * j == x){
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
}

namespace SUB2{
    void solve(){
        int ans = 0;
        for (int u = 1; u * u <= x; u++){
            if (x % u == 0){
                int v = x / u;
                if (u <= n && v <= n) ans += 2;
                if (u == v) ans--;
            }
        }
        cout << ans << endl;
    }
}

void PROGRAM(int _){
    cin >> n >> x;
    if (n <= 1000 && x <= 1000000) SUB1::solve();
    else SUB2::solve();
}

signed main(){
    freopen("BS.inp", "r", stdin);
    freopen("BS.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;
    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

BÀI 3: CHIA TIỀN THƯỞNG

Subtask 1

Sử dụng if-else để liệt kê các khả năng có thể xảy ra.

  • Cả An và Bình không lấy tờ tiền nào.
  • An lấy tờ tiền thứ nhất, Bình lấy tờ tiền thứ hai.
  • An lấy tờ tiền thứ nhất, Bình lấy tờ tiền thứ hai và ba.
  • An lấy tờ tiền thứ hai, Bình lấy tờ tiền thứ nhất. ...

Kiểm tra tất cả các trường hợp và với mỗi trường hợp, kiểm tra xem số tiền An và Bình nắm giữ có bằng nhau không.

Subtask 2

Với mỗi tờ tiền, có ~3~ khả năng có thể xảy ra: An giữ, Bình giữ hoặc được đem đi đầu tư. Ta có thể duyệt qua ~3^n~ khả năng để tìm ra phương án tối ưu nhất sử dụng quay lui.

int n, a[15];
int res = 0;

void ql(int i, int An, int Binh){
    if (i == n + 1){
        if (An == Binh) res = max(res, An);
        return;
    }

    ql(i + 1, An + a[i], Binh); // An giữ tờ tiến thứ i
    ql(i + 1, An, Binh + a[i]); // Bình giữ tờ tiền thứ i
    ql(i + 1, An, Binh); // tờ tiền được đem đi đầu tư
}

Subtask 3

Subtask này ta sẽ sử dụng quy hoạch động.

Gọi ~f[i][diff]~ là lượng tiền đem đi đầu tư ít nhất khi xét đến tờ thứ ~i~ và lượng tiền chênh lệch giữa An và Bình là ~diff~.

Tương tự, vẫn có ~3~ trường hợp có thể xảy ra với tờ tiền thứ ~i~:

  • An giữ: ~f[i][diff] = f[i - 1][diff - a[i]]~
  • Bình giữ: ~f[i][diff] = f[i - 1][diff + a[i]]~.
  • Đem đi đầu tư: ~f[i][diff] = f[i - 1][diff] + a[i]~.

Giá trị của ~f[i][diff]~ là min của 3 trường hợp trên.

Gọi ~sum~ là tổng giá trị của ~n~ tờ tiền. Đáp án bài toán sẽ là ~\frac{sum - f[n][0]}{2}~

Lưu ý:
  • Giá trị của ~diff~ có thể âm ~(-10^5 \le diff \le 10^5)~ nên ta cần cộng thêm biến ~diff~ một lượng ~base~ là ~10^5~ để tránh truy cập vào mảng có index âm.
  • Việc lưu mảng ~f[i][diff]~ cần dùng đến ~500 \times 10^5 \times 2 = 10^8~ int nên sẽ gây tràn bộ nhớ (MLE). Để ý rằng giá trị của ~f[i]~ chỉ dựa vào các ~f[i - 1]~ nên ta chỉ cần duy tri trạng thái của vị trí hiện tại ~i~ và vị trí trước đấy ~i-1~ và cập nhật lần lượt sau khi xét đến vị trí ~i + 1~.

Code tham khảo C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;
const int oo = 1e9;

const int base = 1e5;
const int maxw = 1e5 + 5;
const int maxn = 505;

int n, a[maxn];
int dp[2][maxw + base];

void PROGRAM(int _){
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    int sum = accumulate(a + 1, a + n + 1, 0ll);


    for (int weight = 0; weight <= base * 2; weight++){
        dp[0][weight] = oo;
        dp[1][weight] = oo;
    }

    dp[0][base] = 0;

    for (int i = 1; i <= n; i++){
        for (int w = 0; w <= base * 2; w++){
            if (w + a[i] <= base * 2) dp[1][w] = min(dp[1][w], dp[0][w + a[i]]);
            if (w - a[i] >= 0) dp[1][w] = min(dp[1][w], dp[0][w - a[i]]);
            dp[1][w] = min(dp[1][w], dp[0][w] + a[i]);
        }
        for (int w = 0; w <= base * 2; w++){
            dp[0][w] = dp[1][w];
            dp[1][w] = oo;
        }
    }

    cout << (sum - dp[0][base]) / 2;

}

signed main(){
    freopen("CT.INP", "r", stdin);
    freopen("CT.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

BÀI 4: TRẠM GÁC TRUNG TÂM

Subtask 1

Với subtask này, ta cần tìm cách để cho ~n~ đỉnh của đồ thị liên thông và tổng trọng số cạnh nhỏ nhất. Đây chính là bài toán tìm cây khung nhỏ nhất, có thể sử dụng thuật toán Kruskal hoặc Prim.

Độ phức tạp: ~O(N \times log{N})~.

Subtask 2

Nhận xét: Đồ thị kết nối ~k~ đỉnh đặc biệt sẽ là một đồ thị dạng cây gồm ~k~ đỉnh đặc biệt đó và một vài đỉnh phụ.

Ta tính trước đường đi ngắn nhất qua bất kì hai đỉnh bằng thuật toán Floyd-Warshall trong ~\mathcal{O}(N^3)~ và lưu vào mảng ~dist~.

Gọi ~dp_{mask, i}~ là tổng trọng số của cây kết nối tập ~mask~ đỉnh đặc biệt có gốc là đỉnh ~i~.

Với mỗi ~dp_{mask, i}~, ta cần duyệt qua tất cả các tập con của tập ~mask~, gọi là ~X~. Gọi ~Y = mask \setminus X~. Với cây con gốc ~i~ chứa tập ~X~ đỉnh đặc biệt và cây con gốc ~i~ chứa tập ~Y~ đỉnh đặc biệt, ta có thể gộp chúng lại thành cây con gốc ~i~ chứa tập ~mask~ đỉnh đặc biệt. Cập nhật ~dp_{mask, i} = min(dp_{X, i} + dp_{Y, i})~.

Duyệt qua ~n~ đỉnh. Xét đỉnh ~u~, nếu ~dp_{mask, u} < dp_{mask_i} + dist_{u, i}~, cập nhật lại ~dp_{mask, u} = dp_{mask_i} + dist_{u, i}~. (Ở đây ta lấy cây gốc ~i~ làm cây con gắn vào đỉnh ~u~ để tạo thành cây gốc ~u~).

Độ phức tạp: ~O(N^3 + 3^N \times N + 2^N \times N^2)~

Code tham khảo C++ (Sub 2)

/*
Tag: 
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

const int maxk = 10;
const int maxn = 2e2 + 5;
const int oo = 1e18;

int dp[(1 << 10) + 1][maxn];
int a[maxn];
int d[maxn][maxn];

int n, m, k;

void floyd(){
    for (int k = 1; k <= n; k++){
        for (int u = 1; u <= n; u++){
            for (int v = 1; v <= n; v++){
                if (d[u][v] > d[u][k] + d[k][v]){
                    d[u][v] = d[u][k] + d[k][v];
                }
            }
        }
    }
}



void PROGRAM(int _){
    cin >> n >> m >> k;

    assert(k <= 10);

    for (int i = 0; i < k; i++) cin >> a[i];

    for (int u = 1; u <= n; u++){
        for (int v = u + 1; v <= n; v++){
            d[u][v] = d[v][u] = oo;
        }
    }

    for (int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }

    floyd();

    for (int mask = 0; mask < (1 << k); mask++){
        for (int u = 1; u <= n; u++) dp[mask][u] = oo;
    }

    for (int i = 0; i < k; i++){
        for (int u = 1; u <= n; u++){
            dp[(1 << i)][u] = d[a[i]][u];
        }
    }

    int ans = oo;

    for (int mask = 1; mask < (1 << k); mask++){
        if (__builtin_popcount(mask) == 1) continue;
        for (int i = 1; i <= n; i++){
            for (int mask1 = mask; mask1; mask1 = (mask1 - 1) & mask){
                int mask2 = mask ^ mask1;
                if (!mask1 || !mask2) continue;
                dp[mask][i] = min(dp[mask][i], dp[mask1][i] + dp[mask2][i]);
            }
            for (int u = 1; u <= n; u++){
                dp[mask][u] = min(dp[mask][u], dp[mask][i] + d[u][i]);
            }
        }
    }

    for (int i = 1; i <= n; i++) ans = min(ans, dp[(1 << k) - 1][i]);

    cout << ans << endl;

}

signed main(){
    freopen("TG.INP", "r", stdin);
    freopen("TG.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

BÀI 5: SẮP XẾP HOÁN VỊ

Subtask 1

Duyệt trạng thái ~9!~ để tìm kết quả tối ưu.

Subtask 2

Nhận xét: Trong các cách sắp xếp tối ưu các tập đoạn được chọn để sắp xếp là ~S~ thì với hai đoạn bất kì ~[l_i, r_i]~ và ~[l_j, r_j]~ thì giao của hai đoạn này là rỗng.

Do đó ta có thể quy hoạch động. Gọi ~dp_i~ là chi phí nhỏ nhất để sort từ ~1~ đến ~i~, các vị trí ~i~ phải thỏa mãn ~max(a_1, a_2, ..., a_i) = i~.

Từ đó: ~dp_i = min(dp_j + \lfloor \sqrt{i - j} \rfloor)~ với ~j~ thỏa mãn ~max(a_1, a_2, ..., a_j) = j~.

Độ phức tạp: ~\mathcal{O}(N^2)~.

Subtask 3

Nhận xét:

  • Với dãy độ dài ~n~, chi phí tối đa để sắp xếp lại dãy là ~\lfloor \sqrt{N} \rfloor~ (chọn dãy ~[1..N]~).
  • ~dp_i \geq dp_j~ với ~i \geq j~.

Từ đó, với mỗi ~i~, ta chỉ cần quan tâm tối đa ~\lfloor \sqrt{N} \rfloor~ vị trí ~j~ tương ứng ~\lfloor \sqrt{i - j} \rfloor = 1, 2, ..., \lfloor \sqrt{N} \rfloor~.

Với chi phí ~x~, ta cần tìm vị trí ~j~ nhỏ nhất thỏa mãn ~\lfloor \sqrt{i - j} \rfloor = x~.

~\rightarrow~ ~i - (x + 1)^2 + 1 \le j \le i - x^2~

Gọi ~p_k = j~ là vị trí nhỏ nhất lớn hơn hoặc bằng ~k~ thỏa mãn ~max(a_1, a_2, ..., a_j) = j~. Từ đó ~j = p_{max(0, i-(x+1)^2+1)}~. Cập nhật ~dp_i = dp_j + x~.

Độ phức tạp: ~\mathcal{O}(N\sqrt{N})~.

Subtask 4

Với nhận xét ở subtask 3, ta có thể sử dụng quy hoạch động đổi biến. Gọi:

  • ~dp_x = i~ là vị trí ~i~ lớn nhất có thể sắp xếp tăng dần sử dụng ~x~ chi phí.
  • ~m_i = j~ với ~j~ là giá trị lớn nhất tồn tại hoán vị ~[1..j]~ trong đoạn ~[1..i]~ của dãy ~a~.

Duyệt qua số chi phí từ ~1~ đến ~\lfloor \sqrt{N} \rfloor~ để tính ~dp_i~. Với chi phí ~j < i~ để tính kết quả cho chi phí ~i~, ta có thể sắp xếp tối đa đoạn từ ~[dp_j + 1, min(n, dp_j + (i - j + 1)^2 - 1)]~. Đặt ~pos_j = min(n, dp_j + (i-j+1)^2-1)~, việc chọn sắp xếp đến ~pos_j~ luôn tối ưu bởi ~m_i \geq m_{i-1} \; \forall \; 1 \le i \le n~. Cập nhật ~dp_i=max(m_{pos_j})~.

Lưu ý: nếu ~m_{pos_j}=pos_j~ (~a[1..pos_j]~ là hoán vị từ ~1~ đến ~pos_j~) và ~a_{pos_j+1}=pos_j+1, a_{pos_j+2}=pos_j+2, ..., a_{pos_j+k}=pos_j+k~ thì ta cần cập nhật lại ~dp_i=pos_j+k~.

Độ phức tạp: ~\mathcal{O}(\sqrt{N} \times \sqrt{N}) = \mathcal{O}(N)~

Code C++ tham khảo (Sub 2, 3, 4)

/*
Tag: 
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;

const int maxn = 1e6 + 5;
const int oo = 1e18;

int n, a[maxn];
int sqr[maxn];

void prep(){
    for (int i = 1; i < maxn; i++){
        sqr[i] = sqrtl(i);
    }
}

namespace SUB2{
    const int maxn = 2e3 + 5;

    int dp[maxn];
    int pre[maxn];

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

        for (int i = 1; i <= n; i++){
            if (pre[i] != i){
                dp[i] = oo;
                continue;
            }
            dp[i] = oo;
            if (pre[i - 1] == i - 1) dp[i] = dp[i - 1];
            for (int j = i - 2; j >= 0; j--){
                if (pre[j] == j){
                    dp[i] = min(dp[i], dp[j] + sqr[i - j]);
                }
            }
        }
        cout << dp[n] << endl;

    }
}

namespace SUB3{
    const int maxn = 1e6 + 5;
    int dp[maxn];
    int pre[maxn], p[maxn];


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

        int last = n + 1;
        dp[n + 1] = oo;

        for (int i = n; i >= 1; i--){
            if (pre[i] == i) last = i;
            p[i] = last;
        }

        for (int i = 1; i <= n; i++){
            dp[i] = oo;
            if (pre[i] != i){
                continue;
            }

            if (pre[i - 1] == i - 1) dp[i] = dp[i - 1];

            for (int x = 1; x <= sqr[n]; x++){
                int j = max(0ll, i - (x + 1) * (x + 1) + 1);
                dp[i] = min(dp[i], dp[p[j]] + x);
            }   
        }
        cout << dp[n] << endl;
    }
}

namespace SUB4{
    const int maxn = 1e6 + 5;

    int dp[1005];
    int m[maxn], lg[maxn];
    bool check[maxn];

    void solve(){
        int ins = 1;
        for (int i = 1; i <= n; i++){
            check[a[i]] = true;
            while (check[ins]){
                ++ins;
            }
            m[i] = ins - 1;
        }

        for (int i = n; i >= 1; i--){
            lg[i] = lg[i + 1];
            if (a[i] == i) lg[i]++;
            else lg[i] = 0;
        }



        dp[0] = lg[1];
        if (dp[0] == n){
            cout << 0 << endl;
            return;
        }

        for (int i = 1; i <= sqrt(n); i++){
            for (int j = 0; j < i; j++){
                int pos = min(n, dp[j] + (i - j + 1) * (i - j + 1) - 1);
                dp[i] = max(dp[i], m[pos]);
                if (m[pos] == pos){ // 1 -> pos là hoán vị
                    dp[i] = max(dp[i], m[pos] + lg[pos + 1]);
                }

            }
            if (dp[i] == n){
                cout << i << endl;
                return;
            }

        }
    }
}

void PROGRAM(int _){
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];

    if (n <= 2e3) SUB2::solve();
    else if (n <= 1e5) SUB3::solve();
    else 
    SUB4::solve();
}

signed main(){
    freopen("SX.INP", "r", stdin);
    freopen("SX.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    prep();

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}


Comments

Please read the guidelines before commenting.



  • 4
    bvdung  commented on Sept. 16, 2023, 1:03 p.m. edit 3

    Một "lời giải" khác cho Subtask 4 Bài 5.

    Ta quy hoạch động như Subtask 2, và tính ~dp_i~ theo thứ tự ~i~ chạy từ 1 đến ~n~, đồng thời lưu một cấu trúc dữ liệu ~H~ chứa các hàm dạng ~f_i(x) = a + \sqrt{x - i}~

    Sau khi tính ~dp_i~, nếu ~i~ thỏa mãn ~\max(a_1, a_2, ..., a_i) = i~ thì ta lưu hàm ~f_i(x) = dp_i + \sqrt{x - i}~ vào ~H~.

    Để tính ~dp_i~, ta tìm hàm ~f_j(x)~ thuộc ~H~ sao cho ~f_j(i) = dp_j + \sqrt{i - j}~ là nhỏ nhất, sau đó gán ~dp_i = \lfloor f_j(i) \rfloor = \lfloor dp_j + \sqrt{i - j} \rfloor = dp_j + \lfloor \sqrt{i - j} \rfloor~ (do ~dp_j~ là số nguyên)

    Cấu trúc dữ liệu ~H~ có thể làm được điều trên là cấu trúc dữ liệu bao lồi. Ta kiểm tra ba điều kiện sử dụng cấu trúc dữ liệu bao lồi:

    1, Các hàm trong ~H~ liên tục và có đạo hàm 2 lần tại điểm được truy vấn. Điều này đúng do khi tìm ~f_j(i)~ nhỏ nhất, các hàm ~f_j~ trong ~H~ đều có ~j~ nhỏ hơn ~i~.

    2, Hiệu giữa hai hàm khác nhau bất kì trong ~H~ có nhiều nhất một nghiệm. Xét hàm ~f_i(x) = a_i + \sqrt{x - i}~ và hàm ~f_j(x) = a_j + \sqrt{x - j}~ thuộc ~H~ (~i \ne j~).

    Xét hàm ~g(x) = f_i(x) - f_j(x) = (a_i - a_j) + \sqrt{x - i} - \sqrt{x - j}~

    ~g'(x) = \frac{1}{2}(\frac{1}{\sqrt{x - i}} - \frac{1}{\sqrt{x - j}})~

    Do ~i \ne j~ nên ~g'(x)~ sẽ không đổi dấu. Vẽ bảng biến thiên của ~g(x)~, dễ thấy ~g(x) = 0~ có nhiều nhất một nghiệm ~\Rightarrow f_i(x) - f_j(x)~ có nhiều nhất một nghiệm, nói cách khác, điều kiện 2 thỏa mãn

    3, Đạo hàm cấp 2 của ~f_i~ trong ~H~ không dương trên toàn bộ tập xác định (trong trường hợp dùng ~H~ để tìm ~\min~, trong trường hợp dùng ~H~ để tìm ~\max~ thì đạo hàm cấp 2 phải không âm).

    ~f_i(x) = a + \sqrt{x - i}~; ~f_i'(x) = \frac{1}{2}(x-i)^{-\frac{1}{2}}~; ~f_i''(x) = -\frac{1}{4}(x-i)^{-\frac{3}{2}}~

    Dễ thấy ~f_i~ sẽ luôn không dương trên toàn bộ tập xác định, vì thế điều kiện 3 thỏa mãn.


    • -5
      ngmtuan  commented on Sept. 28, 2023, 8:49 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


      • -1
        ttflres  commented on Sept. 28, 2023, 11:12 a.m.

        Ò v Ó b


  • 4
    bvdung  commented on Sept. 16, 2023, 12:24 p.m.

    Một lời giải khác cho Subtask 1 Bài 5:

    Dễ thấy ~N \leq 9~ nên chi phí tối thiểu sẽ nhỏ hơn bằng ~3~. Ta chia các trường hợp:

    • Trường hợp chi phí bằng ~0~: Đây là trường hợp dãy ~N~ số nguyên dương ban đầu là dãy tăng dần.
    • Trường hợp chi phí bằng ~1~ hoặc ~2~: Đây là trường hợp ta có thể sắp xếp lại tối đa hai dãy con. Ta duyệt các cách sắp xếp một dãy con có thể (có ~O(N^2)~ cách) và các cách sắp xếp hai dãy con có thể (có ~O(N^4)~ cách), với mỗi cách sắp xếp ta sẽ tốn thêm ~O(N\log{N})~ để kiểm tra xem cách sắp xếp có biến dãy ban đầu thành dãy tăng hay không và ~O(1)~ để cập nhật chi phí nhỏ nhất.
    • Nếu không có cách sắp xếp nào có chi phí bằng ~0~, ~1~, ~2~ thì chắc chắn chi phí nhỏ nhất bằng ~3~.

    Độ phức tạp của thuật toán này là ~O(N^5\log{N})~