- Tác giả: ducanhle_
Link contest: https://hnoj.edu.vn/contest/hnoi2022v1
- Hướng dẫn giải chỉ mang tính chất tham khảo. Mọi ý kiến đóng góp và thắc mắc xin báo cho tác giả!
BÀI 1: SỐ CHÍNH PHƯƠNG ĐẶC BIỆT
1. Subtask 1
Với subtask này, có thể duyệt qua tất cả các số trong đoạn ~[a, b]~ và kiểm tra xem số đang xét có phải là số đặc biệt không.
Số ~x~ là số đặc biệt nếu thỏa mãn điều kiện sau:
- ~x~ là số chính phương ~(1)~.
- ~\sqrt{x}~ là số nguyên tố ~(2)~.
Điều kiện ~(1)~ có thể kiểm tra nếu ~\lfloor \sqrt{x} \rfloor \times \lfloor \sqrt{x} \rfloor = x~ thì ~x~ là số chính phương. (~\lfloor x \rfloor~ là số nguyên lớn nhất không vượt quá ~x~).
Điều kiện ~(2)~ có kiểm tra bằng cách duyệt ước trong đoạn ~[2..\sqrt{N}]~.
2. Subtask 2
Việc duyệt qua tất cả các số trong đoạn ~[a, b]~ ở subtask này là bất khả thi bởi ~a \le b \le 10^{12}~.
Ta có nhận xét: Từ ~1~ đến ~10^{12}~ chỉ có tối đa ~10^6~ số chính phương. Từ đó, chỉ cần duyệt qua các số trong đoạn ~[2..10^6]~ và kiểm tra xem số đang xét ~x~ có nguyên tố không. Nếu ~x~ là số nguyên tố thì ta kiểm tra nếu ~a \le x \times x \le b~ thì tăng ~ans~ lên ~1~ đơn vị.
Việc kiểm tra số nguyên tố có thể sử dụng Sàng Eratosthenes.
Code C++ tham khảo
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
using namespace std;
int a, b;
namespace SUB1{
bool scp(int x){
return (int)sqrtl(x) * (int)sqrtl(x) == x;
}
void solve(){
int ans = 0;
for (int i = a; i <= b; i++){
if (scp(i)){
int x = sqrtl(i);
bool check = true;
for (int j = 2; j * j <= x; j++){
if (x % j == 0){
check = false;
break;
}
}
ans += check;
}
}
cout << ans << endl;
}
}
namespace SUB2{
const int maxn = 1e6 + 5;
bool isPrime[maxn];
void sieve(){
fill(isPrime + 2, isPrime + maxn, true);
for (int i = 2; i < maxn; i++){
if (isPrime[i]){
for (int j = i * i; j < maxn; j += i){
isPrime[j] = false;
}
}
}
}
bool inRange(int l, int r, int x){
return l <= x && x <= r;
}
void solve(){
sieve();
int ans = 0;
for (int i = 2; i <= 1000000; i++){
if (isPrime[i] && inRange(a, b, i * i)){
ans++;
}
}
cout << ans << endl;
}
}
void PROGRAM(int _){
cin >> a >> b;
if (b <= 1000000) SUB1::solve();
else SUB2::solve();
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int test = 1;
for (int _ = 1; _ <= test; _++){
PROGRAM(_);
}
return 0;
}
BÀI 2: BẢNG SỐ
Subtask 1
Với ~n \le 10^3~ thì bảng có tối đa ~n \times n \le 10^6~ phần tử. Từ đó, ta có thể dựng cả bảng mảng ~a~ có kích thước ~n \times n~ với ~a[i][j] = i \times j~. Duy trì một biến đếm ~ans~ lưu kết quả rồi duyệt qua mảng ~a~, nếu ~a[i][j] = x~ thì tăng ~ans~ lên ~1~ đơn vị.
Độ phức tạp: ~\mathcal{O}(n^2)~
Subtask 2
Bài toán có thể diễn giải lại như sau: tìm số cặp ~(i, j)~ thỏa mãn ~i \times j = x~ với ~1 \le i \le n, 1 \le j \le n~.
Từ đó, có thể duyệt qua tất cả các ước của ~x~ trong đoạn ~[1..\sqrt{x}]~. Nếu khi duyệt gặp ~u~ là ước của ~x~, gọi ~v = x / u~, ta cần kiểm tra xem nếu ~1 \le u \le n~ và ~1 \le v \le n~ thì tăng ~ans~ lên ~2~ đơn vị nếu ~u \neq v~ (tồn tại hai cặp ~(u, v)~ và ~(v, u)~), lên ~1~ đơn vị nếu ~u = v~.
Độ phức tạp: ~\mathcal{O}({\sqrt{x}})~.
Code C++ tham khảo
/*
Tag:
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
using namespace std;
int n, x;
namespace SUB1{
const int maxn = 1e3 + 5;
void solve(){
int ans = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (i * j == x){
ans++;
}
}
}
cout << ans << endl;
}
}
namespace SUB2{
void solve(){
int ans = 0;
for (int u = 1; u * u <= x; u++){
if (x % u == 0){
int v = x / u;
if (u <= n && v <= n) ans += 2;
if (u == v) ans--;
}
}
cout << ans << endl;
}
}
void PROGRAM(int _){
cin >> n >> x;
if (n <= 1000 && x <= 1000000) SUB1::solve();
else SUB2::solve();
}
signed main(){
freopen("BS.inp", "r", stdin);
freopen("BS.out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
int test = 1;
for (int _ = 1; _ <= test; _++){
PROGRAM(_);
}
return 0;
}
BÀI 3: CHIA TIỀN THƯỞNG
Subtask 1
Sử dụng if-else để liệt kê các khả năng có thể xảy ra.
- Cả An và Bình không lấy tờ tiền nào.
- An lấy tờ tiền thứ nhất, Bình lấy tờ tiền thứ hai.
- An lấy tờ tiền thứ nhất, Bình lấy tờ tiền thứ hai và ba.
- An lấy tờ tiền thứ hai, Bình lấy tờ tiền thứ nhất. ...
Kiểm tra tất cả các trường hợp và với mỗi trường hợp, kiểm tra xem số tiền An và Bình nắm giữ có bằng nhau không.
Subtask 2
Với mỗi tờ tiền, có ~3~ khả năng có thể xảy ra: An giữ, Bình giữ hoặc được đem đi đầu tư. Ta có thể duyệt qua ~3^n~ khả năng để tìm ra phương án tối ưu nhất sử dụng quay lui.
int n, a[15];
int res = 0;
void ql(int i, int An, int Binh){
if (i == n + 1){
if (An == Binh) res = max(res, An);
return;
}
ql(i + 1, An + a[i], Binh); // An giữ tờ tiến thứ i
ql(i + 1, An, Binh + a[i]); // Bình giữ tờ tiền thứ i
ql(i + 1, An, Binh); // tờ tiền được đem đi đầu tư
}
Subtask 3
Subtask này ta sẽ sử dụng quy hoạch động.
Gọi ~f[i][diff]~ là lượng tiền đem đi đầu tư ít nhất khi xét đến tờ thứ ~i~ và lượng tiền chênh lệch giữa An và Bình là ~diff~.
Tương tự, vẫn có ~3~ trường hợp có thể xảy ra với tờ tiền thứ ~i~:
- An giữ: ~f[i][diff] = f[i - 1][diff - a[i]]~
- Bình giữ: ~f[i][diff] = f[i - 1][diff + a[i]]~.
- Đem đi đầu tư: ~f[i][diff] = f[i - 1][diff] + a[i]~.
Giá trị của ~f[i][diff]~ là min của 3 trường hợp trên.
Gọi ~sum~ là tổng giá trị của ~n~ tờ tiền. Đáp án bài toán sẽ là ~\frac{sum - f[n][0]}{2}~
Lưu ý:
- Giá trị của ~diff~ có thể âm ~(-10^5 \le diff \le 10^5)~ nên ta cần cộng thêm biến ~diff~ một lượng ~base~ là ~10^5~ để tránh truy cập vào mảng có index âm.
- Việc lưu mảng ~f[i][diff]~ cần dùng đến ~500 \times 10^5 \times 2 = 10^8~ int nên sẽ gây tràn bộ nhớ (MLE). Để ý rằng giá trị của ~f[i]~ chỉ dựa vào các ~f[i - 1]~ nên ta chỉ cần duy tri trạng thái của vị trí hiện tại ~i~ và vị trí trước đấy ~i-1~ và cập nhật lần lượt sau khi xét đến vị trí ~i + 1~.
Code tham khảo C++
#include <bits/stdc++.h>
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
using namespace std;
const int oo = 1e9;
const int base = 1e5;
const int maxw = 1e5 + 5;
const int maxn = 505;
int n, a[maxn];
int dp[2][maxw + base];
void PROGRAM(int _){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int sum = accumulate(a + 1, a + n + 1, 0ll);
for (int weight = 0; weight <= base * 2; weight++){
dp[0][weight] = oo;
dp[1][weight] = oo;
}
dp[0][base] = 0;
for (int i = 1; i <= n; i++){
for (int w = 0; w <= base * 2; w++){
if (w + a[i] <= base * 2) dp[1][w] = min(dp[1][w], dp[0][w + a[i]]);
if (w - a[i] >= 0) dp[1][w] = min(dp[1][w], dp[0][w - a[i]]);
dp[1][w] = min(dp[1][w], dp[0][w] + a[i]);
}
for (int w = 0; w <= base * 2; w++){
dp[0][w] = dp[1][w];
dp[1][w] = oo;
}
}
cout << (sum - dp[0][base]) / 2;
}
signed main(){
freopen("CT.INP", "r", stdin);
freopen("CT.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
int test = 1;
for (int _ = 1; _ <= test; _++){
PROGRAM(_);
}
return 0;
}
BÀI 4: TRẠM GÁC TRUNG TÂM
Subtask 1
Với subtask này, ta cần tìm cách để cho ~n~ đỉnh của đồ thị liên thông và tổng trọng số cạnh nhỏ nhất. Đây chính là bài toán tìm cây khung nhỏ nhất, có thể sử dụng thuật toán Kruskal hoặc Prim.
Độ phức tạp: ~O(N \times log{N})~.
Subtask 2
Nhận xét: Đồ thị kết nối ~k~ đỉnh đặc biệt sẽ là một đồ thị dạng cây gồm ~k~ đỉnh đặc biệt đó và một vài đỉnh phụ.
Ta tính trước đường đi ngắn nhất qua bất kì hai đỉnh bằng thuật toán Floyd-Warshall trong ~\mathcal{O}(N^3)~ và lưu vào mảng ~dist~.
Gọi ~dp_{mask, i}~ là tổng trọng số của cây kết nối tập ~mask~ đỉnh đặc biệt có gốc là đỉnh ~i~.
Với mỗi ~dp_{mask, i}~, ta cần duyệt qua tất cả các tập con của tập ~mask~, gọi là ~X~. Gọi ~Y = mask \setminus X~. Với cây con gốc ~i~ chứa tập ~X~ đỉnh đặc biệt và cây con gốc ~i~ chứa tập ~Y~ đỉnh đặc biệt, ta có thể gộp chúng lại thành cây con gốc ~i~ chứa tập ~mask~ đỉnh đặc biệt. Cập nhật ~dp_{mask, i} = min(dp_{X, i} + dp_{Y, i})~.
Duyệt qua ~n~ đỉnh. Xét đỉnh ~u~, nếu ~dp_{mask, u} < dp_{mask_i} + dist_{u, i}~, cập nhật lại ~dp_{mask, u} = dp_{mask_i} + dist_{u, i}~. (Ở đây ta lấy cây gốc ~i~ làm cây con gắn vào đỉnh ~u~ để tạo thành cây gốc ~u~).
Độ phức tạp: ~O(N^3 + 3^N \times N + 2^N \times N^2)~
Code tham khảo C++ (Sub 2)
/*
Tag:
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
using namespace std;
const int maxk = 10;
const int maxn = 2e2 + 5;
const int oo = 1e18;
int dp[(1 << 10) + 1][maxn];
int a[maxn];
int d[maxn][maxn];
int n, m, k;
void floyd(){
for (int k = 1; k <= n; k++){
for (int u = 1; u <= n; u++){
for (int v = 1; v <= n; v++){
if (d[u][v] > d[u][k] + d[k][v]){
d[u][v] = d[u][k] + d[k][v];
}
}
}
}
}
void PROGRAM(int _){
cin >> n >> m >> k;
assert(k <= 10);
for (int i = 0; i < k; i++) cin >> a[i];
for (int u = 1; u <= n; u++){
for (int v = u + 1; v <= n; v++){
d[u][v] = d[v][u] = oo;
}
}
for (int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
d[u][v] = min(d[u][v], w);
d[v][u] = min(d[v][u], w);
}
floyd();
for (int mask = 0; mask < (1 << k); mask++){
for (int u = 1; u <= n; u++) dp[mask][u] = oo;
}
for (int i = 0; i < k; i++){
for (int u = 1; u <= n; u++){
dp[(1 << i)][u] = d[a[i]][u];
}
}
int ans = oo;
for (int mask = 1; mask < (1 << k); mask++){
if (__builtin_popcount(mask) == 1) continue;
for (int i = 1; i <= n; i++){
for (int mask1 = mask; mask1; mask1 = (mask1 - 1) & mask){
int mask2 = mask ^ mask1;
if (!mask1 || !mask2) continue;
dp[mask][i] = min(dp[mask][i], dp[mask1][i] + dp[mask2][i]);
}
for (int u = 1; u <= n; u++){
dp[mask][u] = min(dp[mask][u], dp[mask][i] + d[u][i]);
}
}
}
for (int i = 1; i <= n; i++) ans = min(ans, dp[(1 << k) - 1][i]);
cout << ans << endl;
}
signed main(){
freopen("TG.INP", "r", stdin);
freopen("TG.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
int test = 1;
for (int _ = 1; _ <= test; _++){
PROGRAM(_);
}
return 0;
}
BÀI 5: SẮP XẾP HOÁN VỊ
Subtask 1
Duyệt trạng thái ~9!~ để tìm kết quả tối ưu.
Subtask 2
Nhận xét: Trong các cách sắp xếp tối ưu các tập đoạn được chọn để sắp xếp là ~S~ thì với hai đoạn bất kì ~[l_i, r_i]~ và ~[l_j, r_j]~ thì giao của hai đoạn này là rỗng.
Do đó ta có thể quy hoạch động. Gọi ~dp_i~ là chi phí nhỏ nhất để sort từ ~1~ đến ~i~, các vị trí ~i~ phải thỏa mãn ~max(a_1, a_2, ..., a_i) = i~.
Từ đó: ~dp_i = min(dp_j + \lfloor \sqrt{i - j} \rfloor)~ với ~j~ thỏa mãn ~max(a_1, a_2, ..., a_j) = j~.
Độ phức tạp: ~\mathcal{O}(N^2)~.
Subtask 3
Nhận xét:
- Với dãy độ dài ~n~, chi phí tối đa để sắp xếp lại dãy là ~\lfloor \sqrt{N} \rfloor~ (chọn dãy ~[1..N]~).
- ~dp_i \geq dp_j~ với ~i \geq j~.
Từ đó, với mỗi ~i~, ta chỉ cần quan tâm tối đa ~\lfloor \sqrt{N} \rfloor~ vị trí ~j~ tương ứng ~\lfloor \sqrt{i - j} \rfloor = 1, 2, ..., \lfloor \sqrt{N} \rfloor~.
Với chi phí ~x~, ta cần tìm vị trí ~j~ nhỏ nhất thỏa mãn ~\lfloor \sqrt{i - j} \rfloor = x~.
~\rightarrow~ ~i - (x + 1)^2 + 1 \le j \le i - x^2~
Gọi ~p_k = j~ là vị trí nhỏ nhất lớn hơn hoặc bằng ~k~ thỏa mãn ~max(a_1, a_2, ..., a_j) = j~. Từ đó ~j = p_{max(0, i-(x+1)^2+1)}~. Cập nhật ~dp_i = dp_j + x~.
Độ phức tạp: ~\mathcal{O}(N\sqrt{N})~.
Subtask 4
Với nhận xét ở subtask 3, ta có thể sử dụng quy hoạch động đổi biến. Gọi:
- ~dp_x = i~ là vị trí ~i~ lớn nhất có thể sắp xếp tăng dần sử dụng ~x~ chi phí.
- ~m_i = j~ với ~j~ là giá trị lớn nhất tồn tại hoán vị ~[1..j]~ trong đoạn ~[1..i]~ của dãy ~a~.
Duyệt qua số chi phí từ ~1~ đến ~\lfloor \sqrt{N} \rfloor~ để tính ~dp_i~. Với chi phí ~j < i~ để tính kết quả cho chi phí ~i~, ta có thể sắp xếp tối đa đoạn từ ~[dp_j + 1, min(n, dp_j + (i - j + 1)^2 - 1)]~. Đặt ~pos_j = min(n, dp_j + (i-j+1)^2-1)~, việc chọn sắp xếp đến ~pos_j~ luôn tối ưu bởi ~m_i \geq m_{i-1} \; \forall \; 1 \le i \le n~. Cập nhật ~dp_i=max(m_{pos_j})~.
Lưu ý: nếu ~m_{pos_j}=pos_j~ (~a[1..pos_j]~ là hoán vị từ ~1~ đến ~pos_j~) và ~a_{pos_j+1}=pos_j+1, a_{pos_j+2}=pos_j+2, ..., a_{pos_j+k}=pos_j+k~ thì ta cần cập nhật lại ~dp_i=pos_j+k~.
Độ phức tạp: ~\mathcal{O}(\sqrt{N} \times \sqrt{N}) = \mathcal{O}(N)~
Code C++ tham khảo (Sub 2, 3, 4)
/*
Tag:
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
using namespace std;
const int maxn = 1e6 + 5;
const int oo = 1e18;
int n, a[maxn];
int sqr[maxn];
void prep(){
for (int i = 1; i < maxn; i++){
sqr[i] = sqrtl(i);
}
}
namespace SUB2{
const int maxn = 2e3 + 5;
int dp[maxn];
int pre[maxn];
void solve(){
for (int i = 1; i <= n; i++){
pre[i] = max(pre[i - 1], a[i]);
}
for (int i = 1; i <= n; i++){
if (pre[i] != i){
dp[i] = oo;
continue;
}
dp[i] = oo;
if (pre[i - 1] == i - 1) dp[i] = dp[i - 1];
for (int j = i - 2; j >= 0; j--){
if (pre[j] == j){
dp[i] = min(dp[i], dp[j] + sqr[i - j]);
}
}
}
cout << dp[n] << endl;
}
}
namespace SUB3{
const int maxn = 1e6 + 5;
int dp[maxn];
int pre[maxn], p[maxn];
void solve(){
for (int i = 1; i <= n; i++){
pre[i] = max(pre[i - 1], a[i]);
}
int last = n + 1;
dp[n + 1] = oo;
for (int i = n; i >= 1; i--){
if (pre[i] == i) last = i;
p[i] = last;
}
for (int i = 1; i <= n; i++){
dp[i] = oo;
if (pre[i] != i){
continue;
}
if (pre[i - 1] == i - 1) dp[i] = dp[i - 1];
for (int x = 1; x <= sqr[n]; x++){
int j = max(0ll, i - (x + 1) * (x + 1) + 1);
dp[i] = min(dp[i], dp[p[j]] + x);
}
}
cout << dp[n] << endl;
}
}
namespace SUB4{
const int maxn = 1e6 + 5;
int dp[1005];
int m[maxn], lg[maxn];
bool check[maxn];
void solve(){
int ins = 1;
for (int i = 1; i <= n; i++){
check[a[i]] = true;
while (check[ins]){
++ins;
}
m[i] = ins - 1;
}
for (int i = n; i >= 1; i--){
lg[i] = lg[i + 1];
if (a[i] == i) lg[i]++;
else lg[i] = 0;
}
dp[0] = lg[1];
if (dp[0] == n){
cout << 0 << endl;
return;
}
for (int i = 1; i <= sqrt(n); i++){
for (int j = 0; j < i; j++){
int pos = min(n, dp[j] + (i - j + 1) * (i - j + 1) - 1);
dp[i] = max(dp[i], m[pos]);
if (m[pos] == pos){ // 1 -> pos là hoán vị
dp[i] = max(dp[i], m[pos] + lg[pos + 1]);
}
}
if (dp[i] == n){
cout << i << endl;
return;
}
}
}
}
void PROGRAM(int _){
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 2e3) SUB2::solve();
else if (n <= 1e5) SUB3::solve();
else
SUB4::solve();
}
signed main(){
freopen("SX.INP", "r", stdin);
freopen("SX.OUT", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
prep();
int test = 1;
for (int _ = 1; _ <= test; _++){
PROGRAM(_);
}
return 0;
}