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

Author Hung Nguyen Tuong

Bài 1. Số chính phương đặc biệt

Giáo sư Minh mới tìm ra loại số rất đặc biệt và đặt tên là số CPDB. Một số nguyên dương $n$ được gọi là số CPDB nếu $n$ thoả mãn hai tính chất sau:

• $n$ chia hết cho $3$.
• $n$ có đúng $9$ ước số.

Yêu cầu

Giáo sư muốn khảo sát mật độ các số CPDB nên nhờ các bạn tham dự kỳ thi chọn học sinh giỏi lập trình giải quyết bài toán sau: “Cho hai số nguyên không âm $a, b$, hãy đếm số lượng số CPDB trong đoạn $[a,b]$.

Dữ liệu

Vào từ file văn bản CPDB.INP gồm đúng 2 số tự nhiên $a,b$ viết cách nhau.

Kết quả

Ghi ra file văn bản CPDB.OUT gồm số tự nhiên duy nhất là số lượng các số trong đoạn $[a,b]$ có tính chất nêu trên.

Ví dụ

Ràng buộc

• Có $70\%$ số test ứng với $70\%$ số điểm của bài có $a \le b \le 2 \times 10^4$.
• Có $20\%$ số test ứng với $20\%$ số điểm của bài có $a \le b \le 3 \times 10^4$.
• Có $10\%$ số test khác ứng với $10\%$ số điểm của bài có $a \le b \le 3 \times 10^7$.

Lời giải

Trước hết hãy viết và chạy thuật toán trâu để tìm ra quy luật của bài toán.

Giả sử với $a=1, \ b=10000$. Ta lần lượt in ra các số thoả mãn là:

Để ý rằng đây đều là các số chính phương với căn bậc 2 của chúng là:

Từ đây ta có thể thu nhỏ khoảng tính toán từ $3 \times 10^7$ xuống còn $\sqrt{3 \times 10^7} \approx 5500$. Thay vì xét từ $a \to b$, ta chỉ cần xét từ $\sqrt a \to \sqrt b$.

Xét tính chất 1: Chia hết cho $3$. Nếu $n$ chia hết cho $3$ thì hiển nhiên $n^2$ cũng phải chia hết cho $3$.

Xét tính chất 2: Có $9$ ước. Xét $n$ chia hết cho 3, ta phân tích thừa số nguyên tố:

Để $n^2$ có đúng $9$ ước thì chắc chắn $n$ phải có dạng $3^1 \times p^1$ ($p$ là số nguyên tố $\neq 3$) hoặc $n = 3^4 = 81$ (Số ước số).

Tóm lại số CPDB $n$ sẽ thoả mãn 1 trong 2 điều sau:

• $n=81$.
• $n \neq 9$, $n$ chia hết cho $3$ và $n / 3$ là số nguyên tố.

Độ phức tạp: $O(k + k \times \log(\log k))$ với $k \approx \sqrt b$.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
const int maxn = 1e4;
vector<bool> sieve(maxn, true);
void sang(){
    sieve[0] = sieve[1] = false;
    for (int i=2;i*i<=maxn;i++){
        if (sieve[i]){
            for (int j=i*i;j<=maxn;j+=i) sieve[j] = false;
        }
    }
}
bool check(int i){
    if (i==81) return true;
    if (i==9) return false;
    return (i%3==0 && sieve[i/3]);
}
int main()
{
    sang();
    int a, b; cin >> a >> b;
    int ans = 0;
    a = ceil(sqrt(a)), b = floor(sqrt(b));
    for (int i=max(1, a);i<=b;i++){
        if (check(i)) ans++;
    }
    cout << ans;
    return 0;
}

Bài 2. Dãy con

Cho dãy số $A$ gồm $n$ phần tử $A_1,A_2,...,A_n$ và một số nguyên dương $d \ (1 \le d \le n)$. Hãy tìm một đoạn con liên tiếp của dãy $A$ có độ dài $d$ và có tổng các phần tử đạt giá trị lớn nhất (Độ dài của đoạn con là số lượng phần tử trên đoạn con đó).

Yêu cầu

Tính tổng các phần tử trên đoạn con theo yêu cầu như trên.

Dữ liệu

Từ tệp DAYCON.INP có cấu trúc như sau:

• Dòng thứ nhất chứa hai số nguyên dương $n,d \ (1 \le d \le n \le 10^6)$.
• Dòng thứ hai chứa $n$ số nguyên $A_1,A_2,...,A_n$ trong đó $(|A_i| \le 10^4, \ 1 \le i \le n)$.
• Các số nguyên trên cùng một dòng viết cách nhau bởi một dấu cách (space).

Kết quả

Ghi vào tệp DAYCON.OUT gồm một số nguyên duy nhất là tổng các phần tử trên đoạn con tìm được có giá trị lớn nhất.

Ví dụ

Ràng buộc

• Có $45\%$ điểm tương ứng với trường hợp $d \le 3000$ và $n \le 10^4$.
• Có $45\%$ điểm tương ứng với trường hợp $d \le 1000$ và $n = 10^5$.
• Có $10\%$ điểm tương ứng với trường hợp $d \le 1000$ và $n = 10^6$.

Lời giải

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

int main()
{
    int n, d; cin >> n >> d;
    ll a[n], current = 0;
    for (int i=0;i<n;i++){
        cin >> a[i];
        if (i < d) current += a[i];
    }
    ll ans = current;
    for (int i=d;i<n;i++){
        current = current + a[i] - a[i-d];
        ans = max(ans, current);
    }
    cout << ans;
    return 0;
}

Bài 3. Xâu đối xứng

Một trong những vấn đề quan trọng của Tin học là xâu (string). Những kiến thức, thuật toán mới luôn được tìm tòi, phát triển nhanh chóng.

Chắc hẳn bạn cũng đã từng nghe qua về xâu đối xứng. Xâu đối xứng có tính chất: đọc nó từ phải sang trái cũng thu được kết quả giống như đọc từ trái sang phải (còn gọi là xâu palindrome).

Ví dụ về xâu đối xứng như: $thht, \ omo, \ ioi,...$.

Tham dự Hội thi tại trường THPT X, bạn Minh đăng ký tham dự trò chơi RCV, phần thưởng cho người chiến thắng là một chiếc thẻ nhớ 16GB từ ban tổ chức (BTC).

Trò chơi như sau: BTC đưa ra một chuỗi các kí tự chỉ bao gồm các chữ cái in thường từ $a$ đến $z$, và một số bộ $L, R$. Người chơi sẽ trả lời một bộ các câu hỏi của BTC có dạng: “xâu con gồm các kí tự liên tiếp của xâu đã cho từ vị trí $L$ đến $R$ có đối xứng hay không?”.

Yêu cầu

Bạn hãy giúp Minh dành chiến thắng cuộc thi này.

Dữ liệu

Từ tệp D_XUNG.INP có cấu trúc như sau:

• Dòng đầu ghi xâu kí tự không cho biết độ dài.
• Dòng tiếp theo ghi số nguyên dương $k$ - số câu hỏi của BTC.
• $k$ dòng tiếp theo, mỗi dòng ghi hai số nguyên $L,R$.

Kết quả

Ghi vào tệp D_XUNG.OUT gồm $k$ dòng, mỗi dòng ghi tương ứng câu trả lời, nếu có ghi $yes$, ngược lại ghi $no$.

Ví dụ

Ràng buộc

• $50\%$ số test có độ dài xâu $\le 255.$
• $30\%$ số test có độ dài xâu $\le 10^3$.
• Trong tất cả các test độ dài xâu không quá $10^5$ và $k \le 10^5, \ 1 \le L \le R$.

Lời giải

Ý tưởng của thuật toán là với mỗi truy vấn, ta dùng 2 con trỏ chạy từ đầu và cuối của xâu con $s[L...R]$ đến khi gặp nhau.

Nếu ký tự của $s$ tại 2 con trỏ đó khác nhau thì ta kết luận được ngay đó không phải là xâu đối xứng.

Nếu 2 con trỏ đó gặp được nhau, nghĩa là không có cặp ký tự nào khác nhau trong quá trình kiểm tra thì đó là xâu đối xứng.

Với độ phức tạp khá lớn: $O(k \times n)$ với $n$ là độ dài xâu, thì ta chỉ được $80\%$ số điểm của bài.

Để lấy được $20\%$ số điểm còn lại, ta sử dụng kỹ thuật String Hashing.

Đầu tiên ta chọn $p=31, \ m=10^9 + 9$.

Tiếp theo, ta tính trước các mảng sau:

• $\text{p\_pow} [i]$: luỹ thừa modulo $m$ của $p^i$.
• $\text{prefix\_hash}[i]$: hash của xâu con bắt đầu tại $0$ và kết thúc tại $i-1$.
• $\text{suffix\_hash}[i]$: hash của xâu con bắt đầu tại $i-1$ và kết thúc tại $n-1$.

Xâu con $s[L...R]$ là xâu đối xứng khi và chỉ khi hash của $s[L...R]$ bằng với hash của đảo ngược xâu đó. Nghĩa là:

Chi phí tính toán trước chỉ là $O(n)$, và với mỗi truy vấn ta có thể kiểm tra đối xứng trong $O(1)$. Vậy độ phức tạp của thuật toán chỉ còn: $O(\max(n,k))$.

Code

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

const int maxn = 1e5+5, p = 31, m = 1e9+9;
ll prefix_hash[maxn], suffix_hash[maxn], p_pow[maxn];
void precompute(){
    n = s.size();

    p_pow[0] = 1;
    for (int i=1;i<n;i++){
        p_pow[i] = (p_pow[i-1] * p) % m;
    }

    prefix_hash[0] = 0;
    for (int i=0;i<n;i++){
        prefix_hash[i+1] = (prefix_hash[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;
    }
    
    suffix_hash[n+1] = 0;
    for (int i=n-1;i>=0;i--){
        suffix_hash[i+1] = (suffix_hash[i+2] + (s[i] - 'a' + 1) * p_pow[n-i-1]) % m;
    }
}
string solve(int l, int r){
    if (l==r) return "yes";

    ll left_hash = (prefix_hash[r] - prefix_hash[l-1] + m) % m;
    left_hash = (left_hash * p_pow[n-l]) % m;

    ll right_hash = (suffix_hash[l] - suffix_hash[r+1] + m) % m;
    right_hash = (right_hash * p_pow[r-1]) % m;

    return (left_hash == right_hash ? "yes" : "no");
}

int main()
{
    cin >> s;
    precompute();
    int k; cin >> k;
    while (k--){
        int l, r; cin >> l >> r;
        cout << solve(l, r) << nl;
    }
    return 0;
}