- 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
Số
là số chính phương . là số nguyên tố .
Điều kiện
Điều kiện
2. Subtask 2
Việc duyệt qua tất cả các số trong đoạn
Ta có nhận xét: Từ
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
Độ phức tạp:
Subtask 2
Bài toán có thể diễn giải lại như sau: tìm số cặp
Từ đó, có thể duyệt qua tất cả các ước của
Độ phức tạp:
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ó
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
Tương tự, vẫn có
- An giữ:
- Bình giữ:
. - Đem đi đầu tư:
.
Giá trị của
Gọi
Lưu ý:
- Giá trị của
có thể âm nên ta cần cộng thêm biến một lượng là để tránh truy cập vào mảng có index âm. - Việc lưu mảng
cần dùng đến int nên sẽ gây tràn bộ nhớ (MLE). Để ý rằng giá trị của chỉ dựa vào các nên ta chỉ cần duy tri trạng thái của vị trí hiện tại và vị trí trước đấy và cập nhật lần lượt sau khi xét đến vị trí .
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
Độ phức tạp:
Subtask 2
Nhận xét: Đồ thị kết nối
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
Gọi
Với mỗi
Duyệt qua
Độ phức tạp:
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
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à
Do đó ta có thể quy hoạch động. Gọi
Từ đó:
Độ phức tạp:
Subtask 3
Nhận xét:
- Với dãy độ dài
, chi phí tối đa để sắp xếp lại dãy là (chọn dãy ). với .
Từ đó, với mỗi
Với chi phí
Gọi
Độ phức tạp:
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:
là vị trí lớn nhất có thể sắp xếp tăng dần sử dụng chi phí. với là giá trị lớn nhất tồn tại hoán vị trong đoạn của dãy .
Duyệt qua số chi phí từ
Lưu ý: nếu
Độ phức tạp:
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;
}