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

Author Hung Nguyen Tuong

Bài 1. Xâu lặp

Cho $N$ xâu ký tự. Xâu $S_i$ được gọi là xâu lặp nếu nó được tạo thành bằng cách ghép $k$ lần liên tiếp xâu $S_j$ (với $i \neq j, \ 1 \le i,j \le N$ và $k > 1$).

Ví dụ: cho $N=4$ và các xâu: $S_1='XYz', \ S_2='AB', \ S_3='XYZXYZ', \ S_4='ABAB'$. Xâu $S_1$ không được ghép liên tiếp từ một xâu nào trong các xâu còn lại nên không là xâu lặp. Tương tự các xâu $S_2, \ S_3$ cũng không là xâu lặp. Xâu $S_4$ là xâu lặp vì nó được tạo bằng cách ghép $2$ lần liên tiếp xâu $S_2$.

Yêu cầu

Viết chương trình tìm số lượng xâu lặp trong $N$ xâu đã cho.

Dữ liệu

Vào từ tệp văn bản XAULAP.INP gồm:

• Dòng đầu chứa một số nguyên dương $N \ (1 \le N \le 100)$.
• Dòng thứ $i$ trong số $N$ dòng tiếp theo chứa xâu $S_i$ (Độ dài của xâu $S_i$ không quá $255$ kí tự).

Kết quả

Ghi ra tệp văn bản XAULAP.OUT gồm một số nguyên không âm là số lượng xâu lặp tìm được.

Ví dụ

Lời giải

Nếu ta dùng ngay 2 vòng for lồng nhau thì độ phức tạp sẽ là $O(N^2 \times 255)$.

Ta có thể tối ưu hơn một chút bằng cách sắp xếp mảng theo độ dài của xâu.

• Với mỗi $s[i]$, ta chỉ cần xét các $s[j]$ mà độ dài $s[j]$ (đặt là $b$) $\ge 2$ lần độ dài $s[i]$ (đặt là $a$).

Khi đó độ phức tạp sẽ giảm xuống còn: $O \left( \frac{N(N+1)}{2} \times 255 \right)$.

$s[j]$ là lặp của $s[i]$ nếu các điều sau thoả mãn:

• $b\%a=0$.
• Với mỗi ký tự thứ $k \ (0 \le k < b)$ trong $s[j]$ phải thoả mãn: $s[j][k] = s[i][k\%a]$.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
bool cmp(string a, string b){
    return a.size() < b.size();
}
int main()
{
    int n; cin >> n;
    string s[n];
    for (int i=0;i<n;i++){
        cin >> s[i];
    }
    sort(s, s + n, cmp);
    int ans = 0;
    for (int i=0;i<n-1;i++){
        for (int j=i+1;j<n;j++){
            int a = s[i].size(), b = s[j].size(), valid = 1;
            if (a==b || b%a!=0) continue;
            for (int k=0;k<b;k++){
                if (s[j][k] != s[i][k%a]){
                    valid = 0;
                    break;
                }
            }
            ans+=valid;
        }
    }
    cout << ans;
    return 0;
}

Bài 2. Radar

Mỗi quốc gia đều có các thiết bị giám sát bầu trời trên lãnh thổ của mình. Một quốc gia hình chữ nhật được chia lo thành $m$ hàng được đánh số từ $1$ đến $m$ từ trên xuống dưới và $m$ cột được đánh số từ $1$ đến $n$ từ trái sang phải. Lô nằm ở vị trí giao của hàng $i \ (1 \le i \le m)$ và cột $j \ (1 \le j \le n)$ được gọi là lô có toạ độ $(i, j)$. Để giám sát bầu trời, đất nước đó bố trí một số radar tại một số lô. Một radar tại lô $(i,j)$ và khả năng phủ sóng với bán kính $r$ có khả năng nhận biết máy bay nào bay qua trên vùng trời tại các lô $(p,q)$ thoả mãn $i-r \le p \le i+r$ và $j-r \le q \le j+r$.

Yêu cầu

Cho kích thước của quốc gia và vị trí của các lô được bố trí radar cùng với bán kính phủ sóng của radar đó. Hãy xác định tổng số lô nằm trong quốc gia này chưa được giám sát.

Dữ liệu

Vào từ tệp văn bản RADAR.INP có định dạng như sau:

• Dòng đầu ghi hai số nguyên dương $m,n \ (1 \le m,n \le 100)$ là kích thước hàng và cột của lãnh thổ quốc gia. Hai số được ghi cách nhau một dấu cách.
• Dòng thứ hai ghi số nguyên $k \ (1 \le k \le m*n)$ là số các radar được bố trí.
• Trên dòng thứ $i$ trong $k$ dòng tiếp theo ghi ba số nguyên dương $p,q,r \ (1 \le p \le m, \ 1 \le q \le n, \ 1 \le r \le 10)$ tương ứng là toạ độ hàng, cột và bán kính của radar thứ $i$. Giữa các số ghi cách nhau một dấu cách.

Kết quả

Ghi ra tệp văn bản RADAR.OUT một số nguyên dương là tổng số các lô chưa được giám sát.

Ví dụ

Lời giải

Ta sử dụng kỹ thuật loang trên lưới ô vuông.

Mảng bool $\text{visit}$, với $\text{visit}[i][j]$ thể hiện ô $(i,j)$ đã loang đến hay chưa. Ban đầu giả sử mọi $\text{visit}[i][j] = \text{false}$.

Với mỗi toạ độ của radar, ta sẽ tìm được $4$ góc của lưới ô vuông trong bán kính quét được của radar.

Với mỗi góc, nếu tại đó mà chưa loang đến thì sẽ bắt đầu loang từ đó bằng cách sử dụng đệ quy.

Đáp án chính là số ô $(i,j)$ có giá trị là $\text{false}$ sau khi loang xong.

Do các ô được loang đến đã được đánh dấu, nên độ phức tạp chỉ là: $O(m \times n)$.

Code

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

int m, n, k, ans = 0;
int p[mx * mx], q[mx * mx], r;
int visit[mx][mx] = {0};

void flood(int i, int j, int right, int left, int down, int up)
{
    ans++;
    if (j < n && right > 0 && visit[i][j + 1] == 0)
    {
        visit[i][j + 1] = 1;
        flood(i, j + 1, right - 1, 0, down, up);
    }
    if (j > 1 && left > 0 && visit[i][j - 1] == 0)
    {
        visit[i][j - 1] = 1;
        flood(i, j - 1, 0, left - 1, down, up);
    }
    if (i < m && down > 0 && visit[i + 1][j] == 0)
    {
        visit[i + 1][j] = 1;
        flood(i + 1, j, right, left, down - 1, 0);
    }
    if (i > 1 && up > 0 && visit[i - 1][j] == 0)
    {
        visit[i - 1][j] = 1;
        flood(i - 1, j, right, left, 0, up - 1);
    }
}

int main()
{
    cin >> m >> n >> k;
    for (int i = 0; i < k; i++)
    {
        cin >> p[i] >> q[i] >> r;
        if (visit[p[i]][q[i]] == 0)
        {
            ans++;
            visit[p[i]][q[i]] = 1;
        }
        int right = min(q[i] + r, n), left = max(q[i] - r, 1);
        int down = min(p[i] + r, m), up = max(p[i] - r, 1);

        if (visit[down][right] == 0)
        {
            visit[down][right] = 1;
            flood(down, right, 0, r, 0, r);
        }
        if (visit[up][left] == 0)
        {
            visit[up][left] = 1;
            flood(up, left, r, 0, r, 0);
        }
        if (visit[down][left] == 0)
        {
            visit[down][left] = 1;
            flood(down, left, r, 0, 0, r);
        }
        if (visit[up][right] == 0)
        {
            visit[up][right] = 1;
            flood(up, right, 0, r, r, 0);
        }
    }
    cout << m * n - ans;
    return 0;
}

Bài 3. Dãy không giảm (LIS)

Cho dãy số $A$ gồm $N$ số $a_1, a_2, a_3, ..., a_N$. Dãy số $a_{i1}, a_{i2}, ...,a_{ik}$ thoả mãn $a_{i1} \le a_{i2} \le ... \le a_{ik} \ (1 \le i_1 < i_2 < ... < i_k \le N, \ k \ge 1)$ được gọi là dãy con không giảm của dãy $A$. Lưu ý các phần tử của dãy con có thể chọn có thể liên tiếp hoặc không liên tiếp từ các phần tử dãy $A$ nhưng phải theo đúng thứ tự. Độ dài của dãy con là số lượng phần tử của dãy con đó.

Yêu cầu

Hãy tìm độ dài lớn nhất tìm được của dãy con không giảm của dãy $A$.

Dữ liệu

Vào từ tệp văn bản DAYCON.INP gồm 2 dòng:

• Dòng đầu chứa một số nguyên dương $N \ (1 \le N \le 10^5)$ là số phần tử dãy $A.$
• Dòng thứ hai chứa $N$ số nguyên dương $a_i \ (a_i \le 10^5)$, giữa hai số cách nhau bởi một dấu cách.

Kết quả

Ghi ra tệp văn bản DAYCON.OUT một số nguyên dương là độ dài lớn nhất tìm được của dãy con không giảm của dãy $A$.

Ví dụ

Lời giải

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

int main()
{
    int n; cin >> n;
    int a[n];
    for (int i=0;i<n;i++) cin >> a[i];

    const int INF = 1e9;
    vector<int> d(n+1, INF);
    d[0] = -INF;

    for (int i=0;i<n;i++){
        int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
        if (d[l-1] <= a[i] && a[i] < d[l]){
            d[l] = a[i];
        }
    }

    int ans = 0;
    for (int l=0;l<=n;l++){
        if (d[l] < INF) ans = l;
    }
    
    cout << ans;
    return 0;
}