Lời Giải Khảo Sát Đội Tin HQV Đợt 2 2024

Author Hung Nguyen Tuong

Bài 1. EVEN

Lời giải

Ta sẽ đếm số số lẻ từ $1 \to n$, và số số chẵn từ $1 \to n$.

Rồi áp dụng công thức sau:

• Tổng $k$ số lẻ đầu tiên từ $1$:

  $$k^2$$

• Tổng $k$ số chẵn đầu tiên từ $1$:

  $$k\times(k+1)$$

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

ll solve(ll n)
{
    ll even, odd;
    if (n % 2 == 0)
    {
        even = odd = n / 2;
    }
    else
    {
        even = n / 2;
        odd = even + 1;
    }
    return max(odd * odd, even * (even + 1));
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        cout << solve(n) << nl;
    }
    return 0;
}

Bài 2. SUM

Lời giải

Giả sử ban đầu mọi phần tử trong mảng nhân với $1$:

Nếu chọn vị trí $j$ bất kỳ và nhân các phần tử từ vị trí $1 \to j$ với $-1$ thì ta được:

hoặc

Tương tự với $k$ bất kỳ từ $n \to k$:

hoặc

Nhưng nếu ta thực hiện cả 2 thao tác thì luôn có một đoạn con ở giữa sẽ vẫn nhân với $1$ như ban đầu:

Trường hợp $j < k$:

Trường hợp $j=k$:

Trường hợp $j > k$:

Từ các quan sát như vậy ta kết luận được các trường hợp chính như sau:

1. Toàn bộ là $+$.
2. Toàn bộ là $-$.
3. Một đoạn $+$ ở giữa 2 đoạn $-$.
4. Mảng chia thành 2 phần $+,-$.

Vậy từ đây ta có được ý tưởng như sau, kết quả của bài toán chính là giá trị lớn nhất của:

• Tổng của toàn bộ mảng nhân với $1$.
• Tổng của toàn bộ mảng nhân với $-1$.
• $2$ lần tổng lớn nhất của 1 đoạn con liên tiếp trong dãy ban đầu + tổng toàn bộ mảng nhân với $-1$.

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

int main()
{
    int n, a;
    cin >> n;
    int total = 0, current = 0, maxSum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        total += a;
        current = max(a, current + a);
        maxSum = max(maxSum, current);
    }
    cout << 2 * maxSum - total;
    return 0;
}

Bài 3. STRING

Lời giải

Vì chỉ có $26$ ký tự chữ cái Latinh, nên mức độ của chuỗi có giá trị nằm trong khoảng $[1,26]$.

Ý tưởng như sau:

Ta sẽ tính mức độ của tất cả các chuỗi con kết thúc tại vị trí $r \ (0 \le r < n)$. Và sau đó tổng hợp lại các kết quả ấy.

Ví dụ có chuỗi $s = "cabdccbcaa"$.

Giả sử ta cần đếm mức độ của tất cả các chuỗi con kết thúc tại vị trí cuối cùng $r=9$:

Ta thấy rằng số chuỗi con $s[l,9]$ có mức độ:

• $1$ khi $7 < l \le 9$.
• $2$ khi $6 < l \le 7$.
• $3$ khi $3 < l \le 6$.
• $4$ khi $-1 < l \le 3$.

Với $7$ là vị trí xuất hiện cuối cùng của $c$, $6$ là vị trí xuất hiện cuối cùng của $b$, $3$ là vị trí xuất hiện cuối cùng của $d$, $-1$ là toàn bộ chuỗi con kết thúc tại $r$ đều có mức độ là $4$.

Từ đây ta có ý tưởng, với mỗi ký tự có trong chuỗi $s$ khi xét đến $r$, ta sẽ lưu lại vị trí xuất hiện cuối cùng của các ký tự đó vào mảng $p$.

Và sau đó thêm 1 phần tử $-1$, sắp xếp mảng $p$ để tạo ra mảng $x$ như sau:

Vậy ở ví dụ này, số chuỗi con có mức độ $k$ sẽ là:

Trong trường hợp tổng quát hơn ta có $26$ chữ cái Latinh phân biệt, lúc đó mảng $x$ sẽ có $27$ phần tử $[0\ldots26]$:

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

int main()
{
    string s;
    cin >> s;
    vector<int> p(26, -1);
    vector<ll> ans(26, 0);
    for (int i = 0; i < s.size(); i++)
    {
        p[s[i] - 'a'] = i;
        vector<int> x = p;
        x.push_back(-1);
        sort(x.begin(), x.end());
        for (int j = 1; j <= 26; j++)
            ans[26 - j] += x[j] - x[j - 1];
    }

    cout << find(ans.begin(), ans.end(), 0) - ans.begin() << nl;
    for (int i = 0; i < ans.size() && ans[i] != 0; i++)
        cout << ans[i] << nl;

    return 0;
}

Bài 4. DISTANCE

Lời giải

Như đề bài đã cho, đầu vào là 1 cây, nên đây là một đồ thị liên thông, không có chu trình với $N$ đỉnh.

Vì thế đường đi giữa 2 node bất kỳ là duy nhất.

Ta có thể suy ngay được ra là đường đi xa nhất giữa 2 node trong cây sẽ có 2 đầu là 2 node lá. Bởi nếu 1 trong 2 node đấy không phải lá thì có đường đi đó vẫn có thể tiếp tục đi đến node con và tạo ra đường đi xa hơn.

Ta có ý tưởng như sau:

1. DFS từ node gốc cây, để tìm ra node lá xa nhất và lưu lại nốt lá đó gọi là $a$.
2. Rồi lại DFS từ node lá $a$ (giờ ta coi như $a$ là một node gốc) để tìm ra node lá xa nhất gọi là $b$.

Vậy khoảng cách xa nhất giữa 2 đỉnh bất kỳ trên cây chính là khoảng cách giữa $a$ và $b$.

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

const int mx = 2e5 + 2;
vector<vector<int>> adj(mx, vector<int>());
vector<bool> visit(mx);

int fv = -1, md = -1;

void dfs(int u, int d)
{
    visit[u] = true;

    if (d > md)
    {
        md = d;
        fv = u;
    }

    for (auto v : adj[u])
    {
        if (!visit[v])
            dfs(v, d + 1);
    }
}

int main()
{
    int n;
    cin >> n;
    int root = 0;
    for (int i = 1; i <= n; i++)
    {
        int p;
        cin >> p;
        adj[i].push_back(p);
        adj[p].push_back(i);
        if (!p)
            root = i;
    }

    visit.assign(mx, false);
    dfs(root, 0);

    visit.assign(mx, false);
    md = -1;
    dfs(fv, 0);

    cout << md;
    return 0;
}