---
title: Quảng Trị - Kỳ thi HSG lớp 9 cấp Tỉnh - Solution tham khảo
---
$\Huge \text{Kỳ thi HSG lớp 9 cấp Tỉnh - Solution}$
------
:::info
> ✍🏻Writer: [@PhanDat](https://hackmd.io/@AgGV-B2TStmNXQZUbF1pNQ), [@trvhung](https://hackmd.io/@trvhung), [@DucMinh](https://hackmd.io/@phamducminh), [@datma.coder](https://hackmd.io/@datmacoder)
>📋Content:
>[TOC]
>
>[color=blue]
:::
------
## Bài 1 - Đếm số
:::spoiler Tóm tắt đề
> Cho hai số nguyên dương $a$ và $b$.
> **Yêu cầu**: Hãy đếm số lượng số chính phương trong đoạn từ $a$ đến $b$.
:::
### Subtask 1
:::spoiler Editorial
$1 \leq a , b \leq 10^6$
> Với giới hạn này, ta chỉ cần dùng cách duyệt tất cả các số trong đoạn từ $a$ đến $b$ và kiểm tra số đó có phải là số chính phương hay không.
> Một số $x$ nếu là số chính phương khi $k = \lfloor \sqrt{x} \rfloor$ và $k^{2} = x$.
> Độ phức tạp: $O(b - a + 1)$
:::
:::spoiler Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
int a , b , ans = 0;
int32_t main() {
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("CAU1.INP", "r", stdin);
freopen("CAU1.OUT", "w", stdout);
cin >> a >> b;
for (int i = a ; i <= b ; i++) {
int k = sqrt(i);
if (k * k == i) ++ans;
}
cout << ans;
return 0;
}
```
:::
### Subtask 2
:::spoiler Editorial
$10^6 \leq a , b \leq 10^9$
> Một số chính phương có dạng $x = k^2$ $(k \in \mathbb{N})$.
> Ta chỉ cần đếm số lượng số $k$ sao cho $a \leq k^2 \le b$ tương đương với $\sqrt{a} \leq k \leq \sqrt{b}$.
> Vì $k$ phải là số nguyên nên: $k_{min} = \lceil \sqrt{a} \rceil$ và $k_{max} = \lfloor \sqrt{b} \rfloor$.
> Vậy số lượng số chính phương trong đoạn từ $a$ đến $b$ là $k_{max} - k_{min} + 1$.
> Độ phức tạp: $O(1)$
:::
:::spoiler Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
int a , b;
int32_t main() {
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("cau1.inp" , "r" , stdin);
freopen("cau1.out" , "w" , stdout);
cin >> a >> b;
int L = ceil(sqrt(a));
int R = floor(sqrt(b));
cout << R - L + 1;
return 0;
}
```
:::
## Bài 2 - Đếm từ
:::spoiler Tóm tắt đề
> Cho $1$ xâu $S$.
> **Yêu cầu**: Hãy đếm số lượng độ dài khác nhau xuất hiện và với mỗi độ dài đếm số lượng từ có độ dài đó.
:::
### Subtask 1
:::spoiler Editorial
$|S|\leq 10^3$
> Với mỗi độ dài có thể, duyệt lại các từ để đếm số từ có độ dài đó.
> Độ phức tạp: $O(|S|^2)$
:::
:::spoiler Solution
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define el '\n'
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inpout(a) freopen(a".inp","r",stdin), freopen(a".out","w",stdout)
const int maxn = 1e3 + 1;
string s;
vector<string>v;
vector<pair<int, int>>ans;
signed main(){
ios;
inpout("CAU2");
while(cin >> s)
v.push_back(s);
for (int i = 1; i < maxn; ++i){
int cnt = 0;
for (string s: v)
if (s.size() == i)
cnt++;
if (cnt)
ans.push_back(make_pair(i, cnt));
}
cout << ans.size() << el;
for (pair<int, int> x: ans)
cout << x.first << ' ' << x.second << el;
}
```
:::
### Subtask 2
:::spoiler Editorial
$|S| \leq 10^6$
> Nhập vào từng từ, sử dụng 1 mảng để đánh dấu mỗi độ dài có bao nhiêu từ và thêm 1 biến đếm để đếm số độ dài khác nhau.
> Độ phức tạp: $O(|S|)$
:::
:::spoiler Solution
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define el '\n'
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inpout(a) freopen(a".inp","r",stdin), freopen(a".out","w",stdout)
const int maxn = 1e6 + 1;
string s;
int d;
int cnt[maxn];
signed main(){
ios;
inpout("CAU2");
while(cin >> s){
if (!cnt[s.size()])
++d;
++cnt[s.size()];
}
cout << d << el;
for (int i = 1; i < maxn; ++i)
if (cnt[i])
cout << i << ' ' << cnt[i] << el;
}
```
:::
## Bài 3 - Hộp quà
:::spoiler Tóm tắt đề
> Cho mảng số nguyên $a$ gồm $n$ phần tử, các số có giá trị từ 1 tới m.
> **Yêu cầu**: Hãy tìm số nguyên $k$ lớn nhất sao cho với mỗi số $a_i$ mà $1 \leq i \leq k$ thì mỗi số có đúng một số $a_x$ mà $k \lt x \leq n$ sao cho $a_i \lt a_x$ và $x$ phân biệt.
:::
### Subtask 1
:::spoiler Editorial
$1 \leq n \leq 1000, 1 \leq m \leq 10^3$
> Duyệt tất cả các giá trị của $k$, với mỗi $1 \leq i \leq k$ ta tham lam bằng cách tìm vị trí x sao cho $k \lt x \leq n$ và $x$ chưa được sử dụng mà $a_x$ nhỏ nhất có thể nhưng vẫn lớn hơn $a_i$ để thỏa mãn điều kiện.
> Độ phức tạp: $O(n^3)$
:::
:::spoiler Solution
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inpout(a) freopen(a".inp","r",stdin), freopen(a".out","w",stdout)
const int maxn = 1e2 + 5;
int n, m, ans;
int a[maxn];
bool used[maxn];
bool check(int k){
for (int i = k + 1; i <= n; ++i)
used[i] = false;
for (int i = 1; i <= k; ++i){
int x = 0;
for (int j = k + 1; j <= n; ++j)
if (a[j] > a[i] && !used[j] && (x == 0 || a[j] < a[x]))
x = j;
if (!x)
return false;
used[x] = true;
}
return true;
}
signed main(){
ios;
inpout("CAU3");
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
ans = -1;
for (int k = n / 2; k >= 1; --k)
if (check(k)){
ans = k;
break;
}
cout << ans;
}
```
:::
### Subtask 2
:::spoiler Editorial
$100 \leq n \leq 5 * 10^3, 1 \leq m \leq 10^9$
> Thay vì sau mỗi số $a_i$ phải duyệt lại để tìm $x$, ta có thể sắp xếp lại mảng từ $1$ tới $k$ và từ $k+1$ tới $n$ và sự dụng thuật toán $2$ con trỏ để tìm nhanh các vị trí $x$.
> Độ phức tạp: $O(n^2*log(n))$
:::
:::spoiler Solution
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inpout(a) freopen(a".inp","r",stdin), freopen(a".out","w",stdout)
const int maxn = 5e3 + 5;
int n, m, ans;
int a[maxn], arr[maxn];
bool check(int k){
for (int i = 1; i <= n; ++i)
arr[i] = a[i];
sort(arr + 1, arr + k + 1);
sort(arr + k + 1, arr + n + 1);
for (int i = 1, j = k + 1; i <= k; ++i){
while(j <= n && arr[j] <= arr[i])
++j;
if (j > n)
return false;
++j;
}
return true;
}
signed main(){
ios;
inpout("CAU3");
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
ans = -1;
for (int k = n / 2; k >= 1; --k)
if (check(k)){
ans = k;
break;
}
cout << ans;
}
```
:::
### Subtask 3
:::spoiler Editorial
Không ràng buộc gì thêm.
> Nhận thấy nếu $k$ thỏa mãn thì $k-1$ cũng thỏa mãn, ta dùng thuật toán tìm kiếm nhị phân để tìm nhanh $k$.
> Độ phức tạp: $O(n*log(n)^2)$
:::
:::spoiler Solution
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inpout(a) freopen(a".inp","r",stdin), freopen(a".out","w",stdout)
const int maxn = 1e5 + 5;
int n, m;
int a[maxn], arr[maxn];
bool check(int k){
for (int i = 1; i <= n; ++i)
arr[i] = a[i];
sort(arr + 1, arr + k + 1);
sort(arr + k + 1, arr + n + 1);
for (int i = 1, j = k + 1; i <= k; ++i){
while(j <= n && arr[j] <= arr[i])
++j;
if (j > n)
return false;
++j;
}
return true;
}
int cnp(int l, int r){
int ans = -1;
while(l <= r){
int mid = l + r >> 1;
if (check(mid))
l = mid + 1, ans = mid;
else r = mid - 1;
}
return ans;
}
signed main(){
ios;
inpout("CAU3");
cin >> n >> m;
for (int i = 1; i <= n; ++i)
cin >> a[i];
cout << cnp(1, n / 2);
}
```
:::
## Bài 4 - Giá trị của dãy số
:::spoiler Tóm tắt đề
> Cho mảng số nguyên dương $a$ gồm $n$ phần tử.
> **Yêu cầu**: Hãy tính tổng độ chênh lệch của giá trị lớn nhất và giá trị nhỏ nhất của tất cả các đoạn con liên tiếp của dãy.
:::
### Subtask 1
:::spoiler Editorial
$1 \leq n \leq 100$
> Duyệt tất cả các đoạn con liên tiếp, với mỗi đoạn duyệt thêm 1 lần để tìm giá trị lớn nhất và nhỏ nhất.
> Độ phức tạp: $O(n^3)$
:::
:::spoiler Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e2 + 5;
const int INF = 1e9;
int n, a[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
ll res = 0;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j) {
int mx = -INF, mn = INF;
for (int k = i; k <= j; ++k) {
mx = max(mx, a[k]);
mn = min(mn, a[k]);
}
res += mx - mn;
}
cout << res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("CAU4.inp", "r", stdin);
freopen("CAU4.out", "w", stdout);
solve();
return 0;
}
```
:::
### Subtask 2
:::spoiler Editorial
$k \leq 3000$
> Với mỗi đoạn con liên tiếp từ $l$ tới $r$, thay vì phải duyệt lại để tìm giá trị lớn nhất và nhỏ nhất chỉ cần sử dụng lại cặp giá trị đó của đoạn từ $l$ tới $r-1$ để xét cho đoạn hiện tại.
> Độ phức tạp: $O(n^2)$
:::
:::spoiler Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e3 + 5;
const int INF = 1e9;
int n, a[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
ll res = 0;
for (int i = 1; i < n; ++i) {
int mx = a[i], mn = a[i];
for (int j = i + 1; j <= n; ++j) {
mx = max(mx, a[j]);
mn = min(mn, a[j]);
res += mx - mn;
}
}
cout << res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("CAU4.inp", "r", stdin);
freopen("CAU4.out", "w", stdout);
solve();
return 0;
}
```
:::
### Subtask 3
:::spoiler Editorial
Không có ràng buộc gì thêm.
> Bài toán yêu cầu tìm tổng $max - min$ của tất cả đoạn con liên tiếp, ta sẽ tiếp cận bài toán theo hướng với mỗi vị trí $i$, ta tìm "lượng đóng góp" của $a_i$ vào trong kết quả.
>
> Ta xét trường hợp $a_i$ đóng vai trò là $max$ trong công thức kết quả: Giả sử $a_i$ là phần tử lớn nhất trong $mx_i$ đoạn con liên tiếp của dãy thì $a_i$ sẽ đóng góp vào kết quả một lượng là $a_i \times mx_i$.
>
> Tương tự, gọi $mn_i$ là số lượng đoạn con liên tiếp mà $a_i$ đóng vai trò là phần tử nhỏ nhất $min$, thì $a_i$ sẽ đóng góp vào kết quả một lượng là $-(a_i \times mn_i)$.
>
> Như vậy, bài toán chỉ còn là tìm $mx_i$ và $mn_i$ với mọi $1 \leq i \leq n$. Kết quả bài toán sẽ là $\sum_{i=1}^{n} a_i \times (mx_i - mn_i)$.
>
> Lời giải sẽ trình bày cách tìm $mx_i$, $mn_i$ có thể làm tương tự.
>
> Với mỗi $i$, gọi $l_i$ là vị trí **nhỏ nhất** sao cho $1 \leq l_i \leq i$ và $a_i$ là $max$ trong đoạn $(l_i, i)$, gọi $r_i$ là vị trí **lớn nhất** sao cho $i \leq r_i \leq n$ và $a_i$ là $max$ trong đoạn $(i, r_i)$. Dễ thấy rằng mọi đoạn con nhận $a_i$ là $max$ bắt đầu trong khoảng $(l_i, i)$ và kết thúc trong khoảng $(i, r_i)$, vậy $mx_i = (i - l_i + 1) \times (r_i - i + 1)$
>
> Ta có thể tìm $l_i$ và $r_i$ dễ dàng bằng cấu trúc dữ liệu [Stack](https://wiki.vnoi.info/algo/data-structures/Stack) (lưu ý ta phải xử lí biên bằng cách xét thêm dấu bằng ở phần tính $l_i$ hoặc $r_i$, vì có thể có $2$ phần tử giống nhau trong dãy).
>
> Độ phức tạp: $O(n)$
:::
:::spoiler Solution
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int INF = 1e9;
int n, a[N], l_min[N], r_min[N], l_max[N], r_max[N];
stack<int> s;
void precalc_l_r() {
for (int i = 1; i <= n; ++i) {
while (!s.empty() && a[s.top()] >= a[i])
s.pop();
l_min[i] = s.empty() ? 1 : s.top() + 1;
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n; i >= 1; --i) {
while (!s.empty() && a[s.top()] > a[i])
s.pop();
r_min[i] = s.empty() ? n : s.top() - 1;
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = 1; i <= n; ++i) {
while (!s.empty() && a[s.top()] <= a[i])
s.pop();
l_max[i] = s.empty() ? 1 : s.top() + 1;
s.push(i);
}
while (!s.empty()) s.pop();
for (int i = n; i >= 1; --i) {
while (!s.empty() && a[s.top()] < a[i])
s.pop();
r_max[i] = s.empty() ? n : s.top() - 1;
s.push(i);
}
}
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
precalc_l_r();
ll res = 0;
for (int i = 1; i <= n; ++i) {
ll cnt_range_i_max = 1LL * (r_max[i] - i + 1) * (i - l_max[i] + 1);
ll cnt_range_i_min = 1LL * (r_min[i] - i + 1) * (i - l_min[i] + 1);
res += 1LL * a[i] * (cnt_range_i_max - cnt_range_i_min);
}
cout << res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("CAU4.inp", "r", stdin);
freopen("CAU4.out", "w", stdout);
solve();
return 0;
}
```
:::