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

Author Hung Nguyen Tuong

Bài 1. Thống kê chữ cái

Cho một xâu $S$ chỉ gồm các chữ cái tiếng Anh $(a\ldots z,A \ldots Z)$.

Yêu cầu

Bạn hãy thống kê các chữ cái xuất hiện trong xâu $S$ theo thứ tự từ điển và số lần xuất hiện của nó. Việc thống kê các chữ cái không phân biệt chữ hoa, chữ thường.

Dữ liệu

Tệp VANBAN.INP chứa một dòng ghi xâu $S$.

Kết quả

Ghi vào tệp VANBAN.OUT với nội dung:

• Dòng đầu tiên ghi số lượng chữ cái khác nhau có trong xâu $S$ (không phân biệt chữ hoa, chữ thường).
• Mỗi dòng tiếp theo ghi một chữ cái in hoa, tiếp theo là một dấu cách và số lần xuất hiện của nó trong xâu $S$.

Ví dụ

Ràng buộc

• 30% số test ứng với 30% số điểm của bài có độ dài xâu $S$ không lớn hơn $10^2$.
• 30% số test ứng với 30% số điểm của bài có độ dài xâu $S$ không lớn hơn $10^3$.
• 40% số test ứng với 40% số điểm của bài có độ dài xâu $S$ không lớn hơn $10^5$.

Lời giải

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

int main()
{
    string s;
    cin >> s;
    map<char, int> f;
    for (char c : s)
        f[('a' <= c && c <= 'z') ? c - 32 : c]++;

    cout << f.size() << nl;
    for (auto &p : f)
        cout << p.first << " " << p.second << nl;

    return 0;
}

Bài 2. Đoạn thẳng dài nhất

Trên trục số, người ta tô đậm ba đoạn $[L_1, R_1]$, $[L_2, R_2]$ và $[L_3, R_3]$ với các điểm đầu và điểm cuối đều có tọa độ nguyên.

Yêu cầu

Tìm đoạn có độ dài lớn nhất được tô đậm trên trục số từ ba đoạn đã cho.

Dữ liệu

Tệp DOAN.INP gồm 3 dòng, dòng thứ $i$ chứa 2 số nguyên $L_i, R_i ~ (-10^9 \leq L_i \leq R_i \leq 10^9)$, với $i = 1,2,3$, cách nhau bởi dấu cách.

Kết quả

Ghi vào tệp DOAN.OUT một số nguyên là độ dài của đoạn được tô đậm dài nhất trên trục số.

Ví dụ

Ràng buộc

• 30% số test ứng với 30% số điểm trong trường hợp không có hai đoạn nào có điểm chung.
• 30% số test ứng với 30% số điểm trong trường hợp $0 \leq L_i \leq R_i \leq 10^3$.
• 40% số test ứng với 40% số điểm trong trường hợp $-10^9 \leq L_i \leq R_i \leq 10^9$.

Lời giải

Trước tiên, đọc ba đoạn và sắp xếp theo điểm bắt đầu.

Duyệt qua các đoạn. Nếu một đoạn mới giao hoặc chạm với đoạn hiện tại, ta mở rộng đoạn hiện tại. Nếu không, ta chuyển sang đoạn mới.

Trong quá trình này, độ dài lớn nhất của các đoạn liên tục được cập nhật.

Cuối cùng, đưa ra kết quả là đoạn dài nhất được tô đậm.

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

int main()
{
    vector<pair<ll, ll>> s(3);
    for (int i = 0; i < 3; i++)
        cin >> s[i].first >> s[i].second;
    sort(s.begin(), s.end());
    pair<ll, ll> cur = s[0];
    ll ans = cur.second - cur.first;

    for (int i = 1; i < 3; i++)
    {
        if (s[i].first <= cur.second)
            cur.second = max(cur.second, s[i].second);
        else
            cur = s[i];
        ans = max(ans, cur.second - cur.first);
    }
    cout << ans;
    return 0;
}

Bài 3. Tổng các chữ số

Yêu cầu

Bạn hãy đếm số lượng trong đoạn $[L,R]$ có tổng các chữ số bằng $h$ cho trước.

Ví dụ $L=15,R=100,h=10$ thì có $9$ số có tổng các chữ số bằng $10$ đó là $19,28,37,46,55,64,73,82,91$.

Dữ liệu

Vào từ tệp CHUSO.INP gồm một dòng chứa 3 số nguyên $L,R,h$ viết cách nhau bởi dấu cách $(1 \le L \le R \le 10^9, 1 \le h\le 81)$.

Kết quả

Ghi ra tệp CHUSO.OUT gồm số tự nhiên duy nhất là số lượng các số có tổng các chữ số bằng $h$ nằm trong đoạn $[L,R]$.

Ví dụ

Ràng buộc

• Có $30\%$ số test ứng với $30\%$ số điểm của bài có $L \le R \le 10^4$.
• Có $30\%$ số test ứng với $30\%$ số điểm của bài có $L \le R \le 10^6$.
• Có $30\%$ số test khác ứng với $30\%$ số điểm của bài có $L \le R \le 10^9$.

Lời giải

Vì $R$ có thể rất lớn, nên việc tính tổng chữ số từng số từ $L \to R$ là không khả thi.

Chúng ta sẽ áp dụng quy hoạch động trên chữ số (Digit DP).

Tóm tắt đề bài, ta cần tìm số lượng số $x$ sao cho:

• $L \le x \le R$.
• Tổng các chữ số của $x$ là $h$.

Giả sử $f(k,s)$ là số lượng số $x \in [0,k]$ mà tổng các chữ số là $s$, ký hiệu $d(x)=s$.

Vậy số lượng số $x$ trong đề bài cần tìm là:

Vậy làm để có được $f(k,s)$?

Với $k \le 9,s \le 9$ thì việc tính $f(k,s)$ quá đơn giản.

Trường hợp $k>9$, khi $k$ có nhiều chữ số, ta có thể tách $k$ thành 2 phần như sau:

• Chữ số cuối cùng: $r = k \bmod 10$.
• Phần còn lại: $k' = \lfloor k/10 \rfloor$.

Ví dụ: $k=12345 \rightarrow k' = 1234, r=5$.

Và mỗi số $x ~ (0 \le x \le k)$ cũng biểu diễn được như vậy:

• Với $i$ là chữ số cuối $(0 \le i \le 9)$.
• $x'$ là phần còn lại, có số chữ số $\le$ số chữ số của $k'$.

Ta thấy rằng, vì $x \le k$ nên sẽ luôn đảm bảo $x' \le k'$. Nhưng khi ta ghép thêm $i$ vào $x'$ để so sánh với $k$, điều ngược lại chưa chắc đúng. Bởi 2 trường hợp có thể xảy ra:

• $i \le r$: Nếu $x'<k'$ thì chắc chắn $x \le k$, nếu $x'=k'$, hàng đơn vị của $x$ vẫn $\le$ của $k$ nên $x \le k$.
• $i > r$: Nếu $x'<k'$ thì vẫn đảm bảo $x \le k$, nhưng nếu $x'=k'$, hàng đơn vị của $x >$ của $k$ nên $x > k$.

Biết rằng:

Để $d(x) = s$ thì $d(x')$ phải là $s-i$.

Vậy số lượng số $x \in [0,k]$ thoả mãn $d(x)=s$ cũng là số lượng số $x'$ thoả mãn với mỗi $i \in [0,9]$:

• Thêm $i$ vào cuối $x'$ được $x \le k$. Theo quan sát ở trên, ta có $x' \in [0,k'-(i > r)]$.
• $d(x')=s-i$.

Ta suy ra được hàm đệ quy như sau:

Và ta cũng có các trường hợp cơ sở sau:

• $T(k,s)=0$ nếu $(k<0 ~\text{or}~ s < 0)$ hoặc $(k=0 ~\text{và}~ s>0)$.
• $T(k,s)=1$ nếu $k=s=0$.

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

map<pair<int, int>, int> memo;

int T(int k, int s)
{
    if (k < 0 || s < 0)
        return 0;
    if (!k)
        return !s;
    if (memo.find({k, s}) != memo.end())
        return memo[{k, s}];
    int ans = 0;
    for (int i = 0; i <= 9; i++)
        ans += T(k / 10 - (i > (k % 10)), s - i);
    return memo[{k, s}] = ans;
}

int main()
{
    int L, R, h;
    cin >> L >> R >> h;
    cout << T(R, h) - T(L - 1, h);
    return 0;
}

Vì mỗi lần gọi đệ quy ta rút gọn $k$ đi một chữ số. Giả sử ban đầu $k$ có $D$ chữ số $\approx \log_{10}k$, nên chỉ rút gọn $k$ đi $\log_{10}k$ lần. $s$ được giảm từ $h$ xuống $0$, qua mỗi lần đệ quy trừ đi $i \in [0,9]$, nên số các giá trị tối đa $s$ có thể có là $h$. Vậy ta có $s \times \log_{10}k$ trạng thái, mỗi trạng thái duyệt qua $10$ giá trị $i$ là $O(10)$, coi là $O(1)$ vì là hằng số.

Nhờ lưu kết quả trong memo, nên độ phức tạp của thuật toán là $O(h\log R)$.