# Solution bài 1 - Vị trí đặc biệt
## Đề bài
Tóm tắt: Cho dãy $A$ gồm $N$ phần tử, in ra các vị trí $i$ ($i$ khác $1$ và $N$) thỏa mãn $1$ trong $2$ điều kiện:
* $A[i - 1]$ và $A[i + 1]$ là số nguyên tố
* $A[i - 1]$ và $A[i + 1]$ là số chính phương
>[!Note] Lưu ý
>$\rightarrow$ Số nguyên tố là số tự nhiên lớn hơn $1$ chỉ chia hết cho $1$ và chính nó
>VD: $11, 13, 97$
>
>$\rightarrow$ Số chính phương là số tự nhiên mà căn bậc 2 của nó là số nguyên
>VD: $64, 10000$
>>$\sqrt{64} = 8; \sqrt{10000} = 100$
## Subtask 2
### Ý tưởng
Do mảng $A$ không chứa số nguyên tố, nên khi này ta chỉ cần kiểm tra số chính phương
#### **⭐Cách kiểm tra số chính phương**
hàm $sqrt(x) = \sqrt{x}$, hàm $sqrt$ sẽ trả về số thực
lệnh làm tròn xuống là $floor(x)$
* Nếu $x$ là số chính phương, $sqrt(x)$ là số nguyên, làm tròn xuống vẫn bằng chính nó
* Nếu $x$ không phải số chính phương, $sqrt(x)$ không phải là một số nguyên, làm xuống sẽ thành số khác
>VD:
>$sqrt(2) = 1.41421356...$
>làm tròn xuống sẽ là $floor(sqrt(2)) = 1.0$
$\Rightarrow$ Nếu $x$ không phải là số chính phương thì:
==$floor(sqrt(x)) \times floor(sqrt(x)) \ne x$==
Khi này ta dùng $if$ để kiểm tra số chính phương
##### Hàm kiểm tra số chính phương
```cpp=
bool checkCp(int x)
{
if (floor(sqrt(x)) * floor(sqrt(x)) != x)
{
return false;
}
else return true;
}
```
Khi đã có hàm kiểm tra số chính phương, ta chỉ cần $for \space i$ từ $2 \rightarrow N - 1$, nếu thỏa mãn điều kiện thì in ra vị trí $i$
```cpp=
for (int i = 2; i <= N - 1; i++)
{
if (checkCp(A[i - 1]) && checkCp(A[i + 1]))
{
cout << i << " ";
}
}
```
Độ phức tạp $O(N)$
### Code
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool checkCp(int x)
{
if (floor(sqrt(x)) * floor(sqrt(x)) != x)
{
return false;
}
else return true;
}
int A[1000001];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("bai1.inp", "r", stdin);
freopen("bai1.out", "w", stdout);
int N;
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> A[i];
}
for (int i = 2; i <= N - 1; i++)
{
if (checkCp(A[i - 1]) && checkCp(A[i + 1]))
{
cout << i << " ";
}
}
return 0;
}
```
## Subtask 1, 3
### Ý tưởng
Do N nhỏ hoặc $A[i]$ nhỏ, ta có kiểm tra số nguyên tố một cách đơn giản
#### **Kiểm tra nếu $x$ là số nguyên tố**:
$For \space i$ từ $2 \rightarrow x - 1$:
Nếu $x$ chia hết cho $i$ thì có nghĩa $x$ không phải số nguyên tố
##### Hàm kiểm tra số nguyên tố:
```cpp=
bool checkSnt(int x)
{
if (x <= 1) return false;
for (int i = 2; i <= x - 1; i++)
{
if (x % i == 0)
{
return false;
}
}
return true;
}
```
Do cần in ra vị trí các số thỏa mãn số liền trước và liền sau là số nguyên tố trước, sau đó mới in ra vị trí số liền trước và liền sau là số chính phương nên ta sẽ:
* Đưa các vị trí các số thỏa mãn số liền trước và liền sau là số nguyên tố vào $vector \space NT$
* Đưa các vị trí các số thỏa mãn số liền trước và liền sau là số chính phương vào $vector \space CP$
Sau đó lần lượt in ra $2$ $vector$
```cpp=
vector <int> NT, CP;
for (int i = 2; i <= N - 1; i++)
{
if (checkSnt(A[i - 1]) && checkSnt(A[i + 1]))
{
NT.push_back(i);
}
if (checkCp(A[i - 1]) && checkCp(A[i + 1]))
{
CP.push_back(i);
}
}
```
Độ phức tạp $O(N * max(A[i]))$
### Code
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool checkSnt(int x)
{
if (x <= 1) return false;
for (int i = 2; i <= x - 1; i++)
{
if (x % i == 0)
{
return false;
}
}
return true;
}
bool checkCp(int x)
{
return ((int)sqrt(x) * (int)sqrt(x) == x);
}
int A[1000001];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("bai1.inp", "r", stdin);
freopen("bai1.out", "w", stdout);
int N;
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> A[i];
}
vector <int> NT, CP;
for (int i = 2; i <= N - 1; i++)
{
if (checkSnt(A[i - 1]) && checkSnt(A[i + 1]))
{
NT.push_back(i);
}
if (checkCp(A[i - 1]) && checkCp(A[i + 1]))
{
CP.push_back(i);
}
}
for (int i = 0; i < (int)NT.size(); i++)
{
cout << NT[i] << " ";
}
for (int i = 0; i < (int)CP.size(); i++)
{
cout << CP[i] << " ";
}
return 0;
}
```
## Subtask 4
### Ý tưởng
>[!Warning] Kiến thực cần biết
>Sàng nguyên tố
>https://wiki.vnoi.info/algo/algebra/prime_sieve.md
ở sub $4$, do $N$ và $A[i]$ có thể tới $10^5$, nếu kiểm tra số nguyên tố như cách ở sub $1, 3$, ta có thể bị TLE.
Như vậy ta chỉ cần tối ưu phần kiểm tra số nguyên tố bằng sàng nguyên tố
```cpp=
bool isPrime[1000001];
void sang(int n)
{
memset(isPrime, 1, sizeof isPrime);
isPrime[1] = false;
for (int i = 2; i <= n; i++)
{
if (!isPrime[i]) continue;
for (int j = i * i; j <= n; j += i)
{
isPrime[j] = false;
}
}
}
bool checkSnt(int x)
{
return isPrime[x];
}
```
Độ phức tạp $O(N \times log \space log \space N)$
### Code
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool isPrime[1000001];
void sang(int n)
{
memset(isPrime, 1, sizeof isPrime);
isPrime[1] = false;
for (int i = 2; i <= n; i++)
{
if (!isPrime[i]) continue;
for (int j = i * i; j <= n; j += i)
{
isPrime[j] = false;
}
}
}
bool checkSnt(int x)
{
return isPrime[x];
}
bool checkCp(int x)
{
return ((int)sqrt(x) * (int)sqrt(x) == x);
}
int A[1000001];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("bai1.inp", "r", stdin);
freopen("bai1.out", "w", stdout);
sang(1000000);
int N;
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> A[i];
}
vector <int> NT, CP;
for (int i = 2; i <= N - 1; i++)
{
if (checkSnt(A[i - 1]) && checkSnt(A[i + 1]))
{
NT.push_back(i);
}
if (checkCp(A[i - 1]) && checkCp(A[i + 1]))
{
CP.push_back(i);
}
}
for (int i = 0; i < (int)NT.size(); i++)
{
cout << NT[i] << " ";
}
for (int i = 0; i < (int)CP.size(); i++)
{
cout << CP[i] << " ";
}
return 0;
}
```
# Solution bài 2 - Xử lý dữ liệu
## Đề bài
Cho $N$ xâu $S$ lần chứa thông thi các thí sinh bao gồm
* SBD
* Tên
* Giới tính
* Ngày sinh (hợp lệ, chắc chắn sinh năm 2009)
* Điểm
**Các thông tin được ngăn cách với nhau bởi dấu #**
Yêu cầu: tìm ngày sinh được lặp lại nhiều nhất, in ra số lần lặp và các thí sinh mang ngày sinh đó
## ⭐Cách tách tên và ngày sinh
### Ý tưởng
Gọi xâu thông tin là $S$
Nhận thấy rằng các thông tin được ngăn cách bởi dấu '#'
$\Rightarrow$ Ta sẽ tách thông tin bằng cách đếm số lần dấu '#' xuất hiện
Gọi biến $cnt$ là số lần dấu thăng đã xuất hiện khi đang duyệt xâu $S$
Xét ví dụ:
Như vậy, khi ta đang xét ở một kí tự khác #:
* Nếu $cnt = 1$: kí tự ta đang xét thuộc về **tên**
* Nếu $cnt = 3$: kí tự ta đang xét thuộc về **ngày sinh**
Do đó với câu lệnh ==$if \space else$== ta có thể dễ dàng tách tên và ngày sinh ra khỏi xâu $S$
### Code
```cpp=
// tách ngày sinh và tên
int cnt = 0;
string name, ngaySinh;
for (int i = 0; i < S.length(); i++)
{
if (S[i] == '#') cnt++; //đếm số lần xuất hiện của '#'
else if (cnt == 1) // đang duyệt trong thông tin tên
{
name += S[i];
}
else if (cnt == 3) // đang duyệt trong thông tin ngày sinh
{
ngaySinh += S[i];
}
}
```
## Subtask 1
### Ý tưởng
Ở subtask 1, do các ngày sinh đều như nhau:
$\Rightarrow$ Số lần lặp lặp lại của ngày sinh trùng nhiều nhất cũng là số thí sinh cào được ==$= N$==
$\Rightarrow$ Ngày sinh được lặp lại nhiều nhất cũng là ==ngày sinh của thí sinh đầu tiên==
$\Rightarrow$ tất cả thí sinh đều có ngày sinh trùng nên sẽ ==in hết ra $N$ thí sinh==
Khi này nếu là thí sinh đầu tiên ta sẽ in ra ngày sinh sau đó in ra $N$ là số lần lặp, duyệt xong thí sinh nào thì in ra tên thí sinh đó
```cpp=
if (t == 1) //đang là thí sinh đầu tiên, in ra ngày sinh, số lần lặp = N
{
cout << ngaySinh << ' ' << N << '\n';
}
cout << name << '\n';
```
Độ phức tạp:
\begin{equation}
\large O(\sum^{N}_{t} S_t.length())
\end{equation}
### Code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("bai2.inp", "r", stdin);
freopen("bai2.out", "w", stdout);
int N;
cin >> N;
for (int t = 1; t <= N; t++)
{
string S;
cin >> S;
// tách ngày sinh và tên
int cnt = 0;
string name, ngaySinh;
for (int i = 0; i < S.length(); i++)
{
if (S[i] == '#') cnt++; //đếm số lần xuất hiện của '#'
else if (cnt == 1) // đang duyệt trong thông tin tên
{
name += S[i];
}
else if (cnt == 3) // đang duyệt trong thông tin ngày sinh
{
ngaySinh += S[i];
}
}
// subtask 1
if (t == 1)
{
cout << ngaySinh << ' ' << N << '\n';
}
cout << name << '\n';
}
return 0;
}
```
## Subtask 2
### Ý tưởng
Do các thí sinh đều sinh năm $2009$, ta chỉ cần tách ngày và tháng để phân biệt các thí sinh.
$\Rightarrow$ ngày và tháng của thí sinh sẽ nằm ở vị trí ==$0, 1, 3, 4$== trong xâu ngày sinh ta sẽ ghép 4 vị trí đó lại và chuyển thành số để lưu.
>[!Note] Lưu ý:
>Đề bài yêu cầu đưa ra ngày sinh sớm nhất, nên ta sẽ đưa tháng lên trước, sau đó mới tới ngày
```cpp=
string tach = "";
tach += ngaySinh[3];
tach += ngaySinh[4];
tach += ngaySinh[0];
tach += ngaySinh[1];
int so = stoll(tach); //chuyển thành số với hàm stoll
```
Gọi biến $so$ là số sau khi mã hóa từ ngày, tháng sinh
Ta sẽ lưu:
* Danh sách ==tên thí sinh có cùng ngày sinh== đó (==mảng đánh dấu $vector \space nameList$==)
* ==Ngày tháng năm sinh dưới dạng xâu== của ngày sinh đó (==mảng đánh dấu $nS$==)
Khai báo:
```cpp=
string nS[1000001];
vector<string> nameList[1000001];
```
Xử lí
```cpp=
nS[so] = ngaySinh; //Lưu ngày/tháng/năm sinh đại diện
nameList[so].push_back(name); //lưu thêm tên vào danh sách
```
Sau đó, ta chỉ cần duyệt qua mọi số ngày sinh, tìm kiếm ngày sinh có số lượng tên là lớn nhất
Cuối cùng lần lượt in ra ngày/tháng/năm sinh của mã số ngày tháng sinh đó, cùng với danh sách thí sinh có cùng ngày sinh.
```cpp=
int maxx = nameList[0].size();
for (int i = 0; i <= 9999; i++)
{
if (nameList[i].size() > nameList[maxx].size())
{
maxx = i;
}
}
cout << nS[maxx] << " " << nameList[maxx].size() << '\n';
for (int i = 0; i < nameList[maxx].size(); i++)
{
cout << nameList[maxx][i] << '\n';
}
```
Độ phức tạp:
\begin{equation}
\large O(\sum^{N}_{t} S_t.length())
\end{equation}
### Code
```cpp=
#include<bits/stdc++.h>
using namespace std;
string nS[1000001];
vector<string> nameList[1000001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("bai2.inp", "r", stdin);
freopen("bai2.out", "w", stdout);
int N;
cin >> N;
for (int t = 1; t <= N; t++)
{
string S;
cin >> S;
// tách ngày sinh và tên
int cnt = 0;
string name, ngaySinh;
for (int i = 0; i < S.length(); i++)
{
if (S[i] == '#') cnt++; //đếm số lần xuất hiện của '#'
else if (cnt == 1) // đang duyệt trong thông tin tên
{
name += S[i];
}
else if (cnt == 3) // đang duyệt trong thông tin ngày sinh
{
ngaySinh += S[i];
}
}
//tách ngày tháng sinh thành mã số
string tach = "";
tach += ngaySinh[3];
tach += ngaySinh[4];
tach += ngaySinh[0];
tach += ngaySinh[1];
int so = stoll(tach);
//lưu danh sách thí sinh cùng ngày sinh
//lưu ngày/tháng/năm sinh đại diện
nS[so] = ngaySinh;
nameList[so].push_back(name);
}
//Tìm ngày sinh có nhiều thí sinh trùng nhất nhất
int maxx = 0;
for (int i = 0; i <= 9999; i++)
{
if (nameList[i].size() > nameList[maxx].size())
{
maxx = i;
}
}
cout << nS[maxx] << " " << nameList[maxx].size() << '\n';
for (int i = 0; i < nameList[maxx].size(); i++)
{
cout << nameList[maxx][i] << '\n';
}
return 0;
}
```
# Solution bài 3 - Chia bánh
## Đề bài
Cho $A$ gồm $N$ số nguyên, tìm cách chia $N$ số nguyên thành $K$ nhóm liên tiếp, sao cho tổng giá trị tuyệt đối của tổng các giá trị trong $K$ nhóm là lớn nhất
## Subtask 1
### Ý tưởng
Do $N$ số nguyên đề cho là cùng dương hay cùng âm
$\Rightarrow$ Vì vậy chia nhóm như thế nào đều có cùng 1 một kết quả, khi này đáp án là giá trị tuyệt đối của tổng $N$ phần tử
### Code
```cpp=
#include<bits/stdc++.h>
using namespace std;
int A[1000001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("BAI3.INP", "r", stdin);
freopen("BAI3.OUT", "w", stdout);
int N, K;
cin >> N >> K;
for (int i = 1; i <= N; i++)
{
cin >> A[i];
}
long long ans = 0;
for (int i = 1; i <= N; i++)
{
ans += A[i];
}
cout << abs(ans);
return 0;
}
```
## Subtask 2, 3
>[!Warning] Kiến thức cần biết
>Quy hoạch động
### Ý tưởng
Phân tích đề ta thấy:
$\rightarrow$ Với mỗi nhóm không yêu cầu về số lượng hay giá trị của các phẩn tử trong nhóm
$\rightarrow$ Các phần tử được chọn vào nhóm một cách độc lập, không ảnh hưởng đến việc chọn nhóm của giá trị trước hay sau
$\Rightarrow$ Ta chỉ cần quan tâm nhóm đang duyệt hiện tại và thứ tự của nhóm đó.
$\Longrightarrow$ Do đề giới hạn khá nhỏ $N \le 100$ nên ta có công thức QHĐ sau:
Gọi $A$ là mảng bao gồm $N$ phần tử đề cho, đánh số $[1..N]$
Gọi $DP[i][j]$ là tổng độ ngon lớn nhất khi chia $i$ cái bánh đầu tiên thành $j$ đoạn
Với $i, j$ bất kì, ta chạy biến $t$ từ $1$ đến $i$:
==$DP[i][j] = max(\space DP[i][j],\space DP[t - 1][j - 1] + |sum(t, i)| \space )$==
Với $|sum(t, i)|$ là tổng từ $t$ đến $i$
Để tính tổng, ta xây dựng mảng $pf$, với $pf[a]$ là tổng từ $1$ đến $a$
$\Rightarrow$ $|sum(t, i)| = pf[i] - pf[t - 1]$
==$\Longrightarrow$ $DP[i][j] = max(\space DP[i][j],\space DP[t - 1][j - 1] + |pf[i] - pf[t - 1]| \space )$==
Đáp án khi này sẽ là $DP[N][K]$
Độ phức tạp $O(N^2 \times K)$
### Code
```cpp=
#include<bits/stdc++.h>
#define int long long
using namespace std;
int DP[101][101];
int A[101], pf[101];
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
freopen("bai3.inp", "r", stdin);
freopen("bai3.OUT", "w", stdout);
int N, K;
cin >> N >> K;
for (int i = 1; i <= N; i++)
{
cin >> A[i];
pf[i] = pf[i - 1] + A[i];
}
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= K; j++)
{
for (int t = 1; t <= i; t++)
{
DP[i][j] = max(DP[i][j], DP[t - 1][j - 1] + abs(pf[i] - pf[t - 1]));
}
}
}
cout << DP[N][K];
return 0;
}
```
Sign in with Wallet
Connect another wallet