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

Author Hung Nguyen Tuong

Bài 1. Tổng các ước

Có hai số nguyên dương $x, y$.

Yêu cầu

Bạn hãy viết chương trình tính tổng các ước nguyên dương của từng số và tìm tổng lớn hơn trong hai tổng đó, nếu hai tổng có giá trị bằng nhau thì tổng lớn hơn là giá trị bằng nhau đó.

Dữ liệu

Vào từ tệp TONGUOC.INP gồm một dòng ghi hai số nguyên dương $x,y$ viết cách nhau một dấu cách $(1 \le x,y \le 10^{12})$.

Kết quả

Ghi vào tệp TONGUOC.OUT trên một dòng, một số nguyên dương theo yêu cầu bài toán.

Ví dụ

Ràng buộc

• $50\%$ số test ứng với $50\%$ số điểm của bài có: $x,y \le 10^3$.
• $30\%$ số test ứng với $30\%$ số điểm của bài có: $x,y \le 10^7$.
• $20\%$ số test ứng với $20\%$ số điểm của bài có: $x,y \le 10^{12}$.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
ll sumdiv(ll n){
    if (n==1) return 1;
    ll ans = 1 + n;
    for (ll i=2;i*i<=n;i++){
        if (n%i==0){
            if (i*i==n) ans += i ;
            else ans += i + n/i;
        }
    }
    return ans;
}
int main()
{
    ll x, y;
    cin >> x >> y;
    cout << max(sumdiv(x), sumdiv(y));
    return 0;
}

Bài 2. Xâu

Cho số nguyên dương $N$ và xâu $S$ gồm các kí tự là chữ cái $(a,b,...,z,A,B,...,Z)$ viết liền nhau.

Chuẩn hoá xâu $S$ bằng cách chuyển các kí tự chữ cái thường thành các kí tự chữ cái in hoa. Ta quy ước kí tự $'A'$ xuất hiện đầu tiên trong xâu $S$ có giá trị là $1$, kí tự $'A'$ tiếp theo xuất hiện trong xâu $S$ có giá trị là 2, kí tự $'A'$ tiếp theo xuất hiện trong xâu $S$ có giá trị là 3, cứ như thế cho đến cuối xâu $S$. Đối với các kí tự khác cũng quy ước tương tự.

Sau đó tính tổng các giá trị đã được quy ước của xâu $S$.

Ví dụ: nếu $S='cAbbaCAaB'$ thì chuẩn hoá $S='CABBACAAB'$ và quy ước:

• Kí tự $'A'$ xuất hiện $4$ lần nên có các giá trị lần lượt là $1,2,3,4$.
• Kí tự $'B'$ xuất hiện $3$ lần nên có các giá trị lần lượt là $1,2,3$.
• Kí tự $'C'$ xuất hiện $2$ lần nên có các giá trị lần lượt là $1,2$.

⇒ Tổng các giá trị xuất hiện sẽ là $19$.

Yêu cầu

Hãy viết chương trình cho biết tổng các giá trị theo quy ước như trên có chia hết cho số nguyên dương $N$ hay không. Nếu chia hết thì ghi ra tổng đó, nếu không chia hết thì ghi ra số lượng các chữ cái khác nhau của xâu $S$ sau khi chuẩn hoá.

Dữ liệu

Vào từ tệp XAU.INP gồm 2 dòng:

• Dòng 1 chứa số nguyên dương $N \ (1 \le N \le 10^6)$.
• Dòng 2 chứa xâu $S$ (không quá $100000$ kí tự).

Kết quả

Ghi ra tệp XAU.OUT trên một dòng, một số tự nhiên thoả mãn yêu cầu của bài toán.

Ví dụ

Ràng buộc

• Có $40\%$ số test ứng với $40\%$ số điểm của bài với xâu $S$ chỉ xuất hiện ít nhất trong một các kí tự $a,b,c$ hoặc $A,B,C$ và độ dài xâu $S$ tối đa là $1000$ kí tự.
• Có $40\%$ số test ứng với $40\%$ điểm của bài với xâu $S$ có độ dài tối đa $1000$ kí tự.
• Có $20\%$ số test ứng với $20\%$ điểm của bài với xâu $S$ có độ dài tối đa $100000$ kí tự.

Lời giải

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

int main()
{
    ll n, ans = 0; cin >> n;
    string s; cin >> s;
    map<char,int> mp;
    for (auto i : s){
        if ('a' <= i && i <= 'z'){
            ans += ++mp[i-'a'];
        }
        else{
            ans += ++mp[i-'A'];
        }
    }
    if (ans%n==0) cout << ans;
    else cout << mp.size();
    return 0;
}

Bài 3. Dãy số

Cho dãy số $A$ có $N$ số nguyên $a_1,a_2,...,a_n$. Một dãy con liên tiếp các số hạng của dãy $A$ là dãy các số hạng tử số hạng $a_i$ đến số hạng $a_j \ (1 \le i \le j \le N)$.

Yêu cầu

Hãy cho biết dãy $A$ có bao nhiêu dãy con liên tiếp mà giá trị tuyệt đối của tổng các số hạng trong dãy con đó lớn hơn một số nguyên dương $S$ cho trước.

Dữ liệu

Vào từ tệp DAYSO.INP gồm 2 dòng:

• Dòng thứ nhất chứa hai số nguyên $N$ và $S \ (N \le 10^5, \ S \le 10^{14})$.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,...,a_N \ (|a_i| \le 10^9)$.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả

Ghi ra tệp DAYSO.OUT trên một dòng, một số nguyên duy nhất là số dãy con liên tiếp thoả mãn yêu cầu của bài toán.

Ví dụ

Ràng buộc

• Có $30\%$ số test ứng với $30\%$ số điểm của bài có $N \le 100$.
• Có $50\%$ số test ứng với $50\%$ số điểm của bài có $N \le 10^3$.
• Có $20\%$ số test ứng với $20\%$ số điểm của bài có $N \le 10^5$.

Lời giải

Ta sử dụng mảng cộng dồng $\text{pref}$, với $\text{pref}[i]$ là tổng cộng dồn từ đầu mảng đến vị trí $i$.

⇒ Tổng phần tử từ $i \to j$ sẽ là $\text{pref}[j] - \text{pref}[i-1]$.

Theo yêu cầu của bài, cần tìm số đoạn $(i,j)$ sao cho:

Tương đương với 1 trong 2 trường hợp sau:

• $\text{pref}[j] - \text{pref}[i-1] > S$.
• Hoặc $\text{pref}[j]-\text{pref}[i-1] < -S$.

Giả sử ta có $2$ vị trí $u$ và $v$ sao cho $|\text{pref}[v]-\text{pref}[u]| = K > S > 0$.

• Nếu $u<v$ (tổng tuyệt đối của đoạn $(u+1,v)$ là $K$) và:
  • Nếu $\text{pref}[v] > \text{pref}[u]$ thì $\text{pref}[v] - \text{pref}[u] = K \Rightarrow \text{pref}[v] = \text{pref}[u] + K$.
  • Nếu $\text{pref}[v] < \text{pref}[u]$ thì $\text{pref}[v] - \text{pref}[u] = -K \Rightarrow \text{pref}[u] = \text{pref}[v] + K$.
• Tương tự, nếu $v < u$ (tổng tuyệt đối của đoạn $(v+1,u)$ là $K$) và:
  • Nếu $\text{pref}[u] > \text{pref}[v]$ thì $\text{pref}[u] - \text{pref}[v] = K \Rightarrow \text{pref}[u] = \text{pref}[v] + K$.
  • Nếu $\text{pref}[v] < \text{pref}[u]$ thì $\text{pref}[u] - \text{pref}[v] = -K \Rightarrow \text{pref}[v] = \text{pref}[u] + K$.

Ta nhận thấy rằng $u$ ở trước $v$ hay $v$ ở trước $u$ đều không quan trọng.

Nghĩa là với mỗi $u$ bất kỳ, ta chỉ cần tìm $v$ sao cho $\text{pref}[v] = \text{pref}[u] + K$. Cũng như với mỗi $v$ bất kỳ, ta chỉ cần tìm $u$ sao cho $\text{pref}[u] = \text{pref}[v] + K$ với $K > S$.

Từ đó, ta sẽ có ý tưởng sắp xếp mảng $\text{pref}$ theo thứ tự không giảm.

Đến đây, với mỗi vị trí $u$, ta tìm phần tử đầu tiên mà $> \text{pref}[v] + S$, dẫn đến là các phần tử ở sau cũng sẽ $> \text{pref}[v] + S$. Vậy ta có được số vị trí $v$ tương từng với từng vị trí $u$.

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

Code

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

int main()
{
    int n; cin >> n;
    ll s; cin >> s;
    ll pref[n+1], ans = 0;
    pref[0] = 0;
    for (int i=1;i<=n;i++){
        ll a; cin >> a;
        pref[i] = pref[i-1] + a;
    }
    sort(pref, pref + n + 1);
    for (int i=0;i<=n;i++){
        ans += n-(upper_bound(pref, pref + n + 1, pref[i] + s)-pref)+1;
    }
    cout << ans;
    return 0;
}