Lời Giải HSG Tin Tỉnh Quảng Ninh (B) - 2021

Author Hung Nguyen Tuong

Bài 1. Chia lấy dư

Cho 2 số nguyên dương $a, n$. Đặt $S=a+2a+...+na$.

Yêu cầu

Tính số dư của tổng $S$ chia cho $10^9 + 7$.

Dữ liệu

Vào từ file văn bản MOD.INP gồm 2 nguyên dương $a, n \ (1 \le a \le 10^9, \ 1 \le n \le 10^9)$.

Kết quả

Ghi ra file văn bản MOD.OUT số nguyên theo yêu cầu của đề bài.

Ví dụ

Ràng buộc

• Giới hạn 1: $60\%$ số điểm với $a \le 10^3, \ n \le 10^3$.
• Giới hạn 2: $20\%$ số điểm với $a \le 10^9, \ n \le 10^7$.
• Giới hạn 3: $20\%$ số điểm với $a \le 10^9, \ n \le 10^9$.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

const int m = 1e9 + 7;
int main()
{
    ll a, n, csc;
    cin >> a >> n;
    csc = n % 2 == 0 ? (n / 2) % m * (n + 1) % m : ((n + 1) / 2) % m * n % m;
    cout << ((a % m) * csc % m) % m;
    return 0;
}

Bài 2. Thống kê

Thế giới đang phải chống chọi với dịch bệnh COVID-19, nhiều quốc gia trên thế giới có tốc độ lây lan dịch bệnh rất nhanh và biến chủng của virus ngày càng mạnh hơn.

Trong lúc này việc tiêm phòng vắc-xin, khoanh vùng dập dịch đang là vấn đề then chốt để con người chiến thắng dịch bệnh.

Ban chỉ đạo phòng chống dịch bệnh của quốc gia $X$ muốn thống kê số lượng ca F0 của từng địa phương hàng ngày để kịp thời ứng phó, mỗi địa phương lại có nhiều cơ sở y tế khác nhau.

Và khi gửi báo cáo nhanh bằng văn bản về cho ban chỉ đạo phòng chống dịch bệnh, các địa phương gửi theo cấu trúc chung như ví dụ dưới đây:

(Tức là địa phương trên có 4 cơ sở y tế với số F0 lần lượt là: 3, 20, 30, 5).

Yêu cầu

Bạn hãy lập trình giúp quốc gia $X$ tính nhanh tổng các ca F0 của từng địa phương và tìm ra địa phương nào đang có số ca F0 cao nhất.

Dữ liệu

Vào từ file văn bản THONGKE.INP gồm:

• Dòng thứ nhất: Chứa số nguyên $N \ (1 \le N \le 100)$ là số lượng địa phương đã báo cáo.
• $N$ dòng tiếp theo: Mỗi dòng chứa 1 văn bản báo cáo theo mẫu chung của từng địa phương với độ dài không quá $10^5$ kí tự.

Kết quả

Ghi ra file văn bản THONGKE.OUT gồm:

• Dòng thứ nhất: Ghi số ca F0 cao nhất theo yêu cầu đề bài.
• $N$ dòng tiếp theo: Mỗi dòng ghi số lượng ca F0 của từng địa phương, thứ tự giống báo cáo ban đầu.

Ví dụ

Ràng buộc

• Giới hạn 1: $50\%$ số điểm với số ca F0 của các cơ sở y tế là nhỏ hơn $10$ ca.
• Giới hạn 2: $50\%$ số điểm với số ca F0 của các cơ sở y tế là nhỏ hơn $100.000$ ca.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int main()
{
    int t;
    cin >> t;
    ll mx = -1;
    string ans = "";

    while (t--)
    {
        string s, tmp;
        cin >> s;
        stringstream ss(s);

        ll total = 0;
        while (getline(ss, tmp, '-'))
        {
            ll cnt = 0;
            for (int i = 0; i < tmp.size() - 2; i++)
            {
                cnt = cnt * 10 + (int)tmp[i] - 48;
            }
            total += cnt;
        }

        mx = max(mx, total);
        ans += to_string(total) + nl;
    }

    cout << mx << nl << ans;
    return 0;
}

Bài 3. Tham quan

Trong một khu du lịch sinh thái rộng lớn, có rất nhiều địa điểm vui chơi - khám phá khác nhau. Du khách có thể tham quan các địa điểm bằng cách ngồi xe ô tô điện của khu du lịch.

Giá vé của mỗi lộ trình ô tô điện khác nhau được ghi dưới dạng dãy $A$ gồm $n \ (1 \le n \le 10^5)$ số nguyên dương $A_1,A_2,...,A_n \ (10^4 \le A_i \le 10^5, \ 1 \le i \le n)$. Trong đó $A_1$ là giá vé từ khu vực xuất phát đến địa điểm tham quan đầu tiên, $A_i$ là giá vé từ địa điểm thứ $i-1$ đến địa điểm thứ $i$.

Gọi số nguyên $m \ (1 \le m \le 10^5)$ là số lượng du khách, dãy $B$ gồm các số nguyên dương $B_1,B_2,...,B_m \ (0 \le B_j \le 10^{10}, \ 1 \le j \le m)$. Trong đó $B_j$ là số tiền mà vị khách thứ $j$ đang có.

Yêu cầu

Hãy lập trình tính số lượng địa điểm mà lần lượt từng du khách có thể đi nhiều nhất bằng cách ngồi ô tô điện với số tiền của từng người mang theo.

Chú ý du khách chỉ được mua vé tham quan bằng ô tô điện từ khu vực xuất phát và phải mua theo lộ trình liên tục.

Dữ liệu

Vào từ file văn bản THAMQUAN.INP gồm:

• Dòng 1 chứa 2 số nguyên dương $n,m$.
• Dòng 2 chứa $n$ số nguyên dương $A_1,A_2,...,A_n$.
• Dòng 3 chứa $m$ số nguyên dương $B_1,B_2,...,B_m$.

Kết quả

Ghi ra file văn bản THAMQUAN.OUT một dòng duy nhất theo yêu cầu bài toán. Mỗi số cách nhau một dấu cách.

Ví dụ

Ràng buộc

• Giới hạn 1: $20\%$ số điểm với $n \le 10, \ m=1$.
• Giới hạn 2: $20\%$ số điểm với $n,m \le 10^3$.
• Giới hạn 3: $60\%$ số điểm với $n,m \le 10^5$.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int main()
{
    int n, m;
    cin >> n >> m;
    vector<ll> pref(n + 1);
    pref[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        ll A;
        cin >> A;
        pref[i] = A + pref[i - 1];
    }
    for (int i = 0; i < m; i++)
    {
        ll B;
        cin >> B;
        cout << upper_bound(pref.begin(), pref.end(), B) - pref.begin() - 1 << " ";
    }
    return 0;
}

Bài 4. Tạo test

Bài giảng về quy hoạch động được minh hoạ bằng bài toán tìm đường đi trên lưới ô vuông như sau.

Cho lưới ô vuông hình chữ nhật có $m$ dòng và $n$ cột. Mỗi ô $(i,j)$ của lưới có ghi một số nguyên $a_{ij} \ (i=1,2,...,m; \ j=1,2,...,n)$. Từ mỗi ô chỉ có thể di chuyển sang ô kề cạnh bên phải hoặc xuống dưới (nếu tồn tại ô đến).

Giá trị đường đi là tổng các số ghi trên những ô nằm trên đường đi. Hãy tìm đường đi có giá trị lớn nhất, xuất phát từ ô trên trái và kết thúc ở ô dưới phải. Đường đi này được gọi là đường đi tối ưu.

Bài giảng trên được mở rộng và nâng cao ở buổi ngoại khoá cho học sinh giỏi. Một loạt các test được tạo ra để kiểm tra chương trình của học sinh.

Xây dựng test mới là một việc khó và buồn tẻ. Vì vậy thầy giáo thông báo là sử dụng các test cũ đã có, nhưng ở mỗi test giá trị của một ô bị thay đổi thành số cực nhỏ (có thể bằng 0 hoặc âm) để đường đi tối ưu không còn được như cũ và giá trị đường đi tối ưu mới sẽ là nhỏ nhất trong số các khả năng giá trị một ô bị thay đổi. Ô trên trái và ô dưới phải vẫn giữ nguyên giá trị cũ.

Hình vẽ sau minh hoạ cho ví dụ ở dưới.

Yêu cầu

Cho test ban đầu, hãy xác định giá trị của đường đi tối ưu mới sau khi thay đổi giá trị ở một ô theo điều kiện đã nêu.

Dữ liệu

Vào từ file văn bản TEST.INP:

• Dòng đầu tiên chứa 2 số nguyên $m,n \ (2 \le m,n \le 1500)$.
• Dòng thứ $i$ trong $m$ dòng sau chứa $n$ số nguyên $a_{i1},a_{i2},...,a_{in} \ (1 \le a_{ij} \le 10^9)$.

Kết quả

Ghi ra file văn bản TEST.OUT một số nguyên dương duy nhất là giá trị đường đi tối ưu mới

Ví dụ

Ràng buộc

• Giới hạn 1: $60\%$ số điểm với $2 \le m,n \le 50$.
• Giới hạn 2: $20\%$ số điểm với $2 \le m,n \le 300$.
• Giới hạn 3: $20\%$ số điểm không có thêm ràng buộc nào.

Lời giải

Sử dụng Quy hoạch động.

Ý tưởng:

• Đầu tiên, tìm ra đi đường đi tối ưu ban đầu và lưu lại từng ô trong đường đi đó.
• Với mỗi ô trong đường đi đó, thay đổi giá trị đến âm vô cùng, sau đó tìm ra đường đi tối ưu khác mà không đi qua ô đó.
• Kết quả của bài toán là $\min$ của các đường đi tối ưu khác.

Cài đặt:

• $\text{dp1}[i][j]$ là đường đi tối ưu từ góc trái trên cùng đến ô $(i,j)$.

  $$\Rightarrow \text{dp1}[i][j] = \max(\text{dp1}[i-1][j], \text{dp1}[i][j-1]) + a[i][j]$$

• $\text{dp2}[i][j]$ là đường đi tối ưu từ góc phải dưới cùng đến ô $(i,j)$.

  $$\Rightarrow \text{dp2}[i][j] = \max(\text{dp2}[i+1][j], \text{dp2}[i][j+1]) + a[i][j]$$

• $\text{trace}[i][j]$ là từ ô nào đi đến ô $(i,j)$ trong đường đi tối ưu ban đầu.

Giả sử $(i,j)$ là một ô trong đường đi tối ưu, nếu ta thay giá trị ô đó thành vô cùng nhỏ thì ta sẽ chia lưới ô vuông ban đầu thành 2 vùng, vùng 2 là lưới ô vuông chứa $(i,j)$ và ô góc phải dưới cùng, vùng 1 là vùng còn lại, để có thể đi từ nơi xuất phát đến đích (nghĩa là phải đi từ vùng 1 đến được vùng 2), ta phải đi:

• Từ trên xuống: $(i-1,j+1) \to (i,j+1)$, hoặc $(i-1,j+2) \to (i,j+2)$, hoặc $(i-1,j+3) \to (i,j+3)$, hoặc… $(i-1,n) \to (i,n)$.
• Hoặc từ trái sáng: $(i+1,j-1) \to (i+1,j)$, hoặc $(i+2,j-1) \to (i+2,j)$, hoặc… $(m,j-1) \to (m,j)$.
• Ta cần lấy $\max$ của những hướng đi đó.

Vì vậy ta cần tính thêm trước 2 mảng để tìm ra $\max$ của của những hướng đi trong $O(1)$.

• $a[i][j]$ (sử dụng lại mảng $a$ để tối ưu bộ nhớ) là đường đi tối ưu nhất với chiều đi từ trên xuống dưới nếu ô $(i,j-1)$ bị thay đổi giá trị đến $-\infty$.

  $$\Rightarrow a[i][j] = \max(\text{dp1}[i-1][j] + \text{dp2}[i][j], a[i][j+1])$$

• $b[i][j]$ là đường đi tối ưu nhất với chiều đi từ ô bên trái sang ô bên phải nếu ô $(i-1,j)$ bị thay đổi giá trị đến $-\infty$.

  $$\Rightarrow b[i][j] = \max(\text{dp1}[i][j-1] + \text{dp2}[i][j], b[i+1][j])$$

Ta sẽ truy dấu vết của đường đi tối ưu ban đầu qua mảng $\text{trace}$ bắt đầu từ ô góc phải dưới cùng. Với mỗi ô $(i,j)$ trên đường đi bị thay đổi ta sẽ chọn $\max$ trong hai trường hợp:

• Đi theo hướng từ trên xuống dưới từ vùng 1 sang vùng 2.

• Đi theo hướng từ trái sang phải từ vùng 1 sang vùng 2.

  $$\Rightarrow ans = \min(ans, \max(b[i+1][j], a[i][j+1]))$$

Độ phức tạp: $O(m \times n)$.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int main()
{
    int m, n;
    cin >> m >> n;
    vector<vector<ll>> a(m + 2, vector<ll>(n + 2, LLONG_MIN)),
        b(m + 2, vector<ll>(n + 2, LLONG_MIN)),
        dp1(m + 1, vector<ll>(n + 1)),
        dp2(m + 1, vector<ll>(n + 1));
    vector<vector<char>> trace(m + 1, vector<char>(n + 1));

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

    // tren trai -> duoi phai
    dp1[1][1] = a[1][1];
    trace[1][1] = 'x';
    for (int i = 2; i <= m; i++)
    {
        dp1[i][1] = a[i][1] + dp1[i - 1][1];
        trace[i][1] = 'u';
    }
    for (int i = 2; i <= n; i++)
    {
        dp1[1][i] = a[1][i] + dp1[1][i - 1];
        trace[1][i] = 'r';
    }
    for (int i = 2; i <= m; i++)
    {
        for (int j = 2; j <= n; j++)
        {
            if (dp1[i - 1][j] > dp1[i][j - 1])
            {
                dp1[i][j] = dp1[i - 1][j] + a[i][j];
                trace[i][j] = 'u';
            }
            else
            {
                dp1[i][j] = dp1[i][j - 1] + a[i][j];
                trace[i][j] = 'r';
            }
        }
    }

    // duoi phai -> tren trai
    dp2[m][n] = a[m][n];
    for (int i = m - 1; i >= 1; i--)
    {
        dp2[i][n] = a[i][n] + dp2[i + 1][n];
    }
    for (int i = n - 1; i >= 1; i--)
    {
        dp2[m][i] = a[m][i] + dp2[m][i + 1];
    }
    for (int i = m - 1; i >= 1; i--)
    {
        for (int j = n - 1; j >= 1; j--)
        {
            dp2[i][j] = max(dp2[i + 1][j], dp2[i][j + 1]) + a[i][j];
        }
    }

    // tren xuong
    for (int i = 2; i <= m; i++)
    {
        for (int j = n; j >= 1; j--)
        {
            a[i][j] = max(dp1[i - 1][j] + dp2[i][j], a[i][j + 1]);
        }
    }
    // trai sang
    for (int j = n; j >= 2; j--)
    {
        for (int i = m; i >= 1; i--)
        {
            b[i][j] = max(dp1[i][j - 1] + dp2[i][j], b[i + 1][j]);
        }
    }

    int row = m, col = n;
    ll ans = LLONG_MAX;
    while (1)
    {
        if (!((row == 1 && col == 1) || (row == m && col == n)))
        {
            ans = min(ans, max(b[row + 1][col], a[row][col + 1]));
        }
        if (trace[row][col] == 'u')
            row--;
        else if (trace[row][col] == 'r')
            col--;
        else
            break;
    }

    cout << ans;
    return 0;
}