Codeforces Solution

Cho dải ruy băng chiều dài n, và 3 số a, b, c. Bạn cần tìm số mảnh vải a, b, c mà nó có thể cắt đúng thành dải duy băng n

Input :

5 5 3 2
              

Ouput :

2
              

Giải thích : miếng vải b và c lần lượt là 3 và 2, 2 miếng vải này cộng lại đủ thành chiều dài ruy băng chiều dài n

Bài này sử dụng Dynamic Programming, vì giới hạn bài khá nhỏ (1 ≤ n, a, b, c ≤ 4000).

Gọi trạng thái dp[i] là số đoạn tối đa có thể tạo thành tổng i.

• 🔹 Công thức truy hồi : dp[i] = max(dp[i], dp[i - a] + 1)
• 🔹 Để tạo tổng i hợp lệ:
  • ✔️ Nếu dp[i - a] đã được chọn → dp[i - a] ∈ {a, b, c}
  • ❌ Nếu dp[i - a] chưa được chọn → dp[i - a] ∉ {a, b, c}

Quy trình thực hiện:

• 🟢 Bước 1: Khởi tạo dp với giá trị -1 (chưa có mảnh vải hợp lệ).
• 🟡 Bước 2: Đặt dp[0] = 0 vì không cần chọn bất kỳ đoạn nào.
• 🔵 Bước 3: Duyệt qua các giá trị i từ 1 → n để tính toán tối ưu.

📋 Copy

#include <bits/stdc++.h>
using namespace std;

#define mem(a,b) memset(a, b, sizeof(a))
#define all(a) a.begin(), a.end()
#define sz(A) (int) A.size()
#define faster() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int N = 1e5 + 15;
int dp[4004];
void __init__() {mem(dp, -1); dp[0] = 0;} 
void solve() {
    __init__();
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    for(int i = 1; i <= n; i++) {
        if(i >= a && dp[i - a] != -1) dp[i] = max(dp[i], dp[i - a] + 1);
        if(i >= b && dp[i - b] != -1) dp[i] = max(dp[i], dp[i - b] + 1);
        if(i >= c && dp[i - c] != -1) dp[i] = max(dp[i], dp[i - c] + 1);
    }
    cout << dp[n] << endl;
}
      
int main(){
    faster()
    solve();
    return 0;
}

Cho một chuỗi s, cần tìm chuỗi con t thỏa mãn:

• t là tiền tố của s (bắt đầu chuỗi).
• t là hậu tố của s (kết thúc chuỗi).
• t có chuỗi con ở giữa trùng với hậu tố và tiền tố
• Trong các chuỗi thỏa mãn, chọn chuỗi dài nhất. Nếu không có, trả về "Just a legend".

Input :

fixprefixsuffix
              

Ouput :

fix
              

Giải thích : vì fix là tiền tố xuất hiện ở đầu chuỗi, giữa chuỗi và cả ở kết thúc chuỗi.

Bài này sử dụng Hash string, KMP, Z-Function,..., nhưng mình sẽ dùng Hash string, vì dễ cài đặt và rất dễ sử dụng

Gọi k là độ dài chuỗi con của chuỗi s (1 -> s.length()).

• 🔹 Ta sẽ có công thức Tiền tố và Hậu tố lần lượt là
• ✔️ Tiền tố getHash(1, k)
• ✔️ Hậu tố getHash(n - k + 1, n)

Quy trình thực hiện:

• 🟢 Bước 1: Khởi tạo Pow và Hash strong hàm __init__() và hàm getHash() lấy giá trị truy vấn
• 🟡 Bước 2:Duyệt qua các giá trị k từ 1 → n để lấy các đoạn Tiền tố và Hậu tố có giá trị truy vấn bằng nhau và cho vào 1 vector, sắp xếp theo thứ tự giảm dần, vì ta cần lấy chuỗi dài nhất và tránh bị timelimit.
• 🔵 Bước 3:Duyệt qua các giá trị i từ 2 → n - k để kiểm tra có tồn tại 1 chuỗi con k ở giữa, có cả hậu tố và tiền tố không bằng cách so sánh getHash(i, i + k - 1) == getHash(1, k) lần lượt là đoạn con cần tìm(ở giữa) và tiền tố có độ dài là k.
• 🔴 Bước 4:Nếu tìm thấy thì output kết quả và thoát khỏi chương trình, ta cần duyệt theo thứ tự giảm dần để không cần duyệt các giá trị nhỏ hơn, gây time limit.

📋 Copy

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mem(a,b) memset(a, b, sizeof(a))
#define all(a) a.begin(), a.end()
#define sz(A) (int) A.size()
#define faster() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
                
const int base = 31;
const ll MOD = 1e9 + 9;
vector<ll>Pow, Hash, a;
string s;
int n, N;
                
ll getHash(int l, int r) {
return (Hash[r] - Hash[l - 1] * Pow[r - l + 1] % MOD + MOD) % MOD;
}
                
void __init__() {
s = ' ' + s;
n = s.length() - 1;
Pow.resize(n + 1);
Hash.resize(n + 1);
Pow[0] = 1;
for(int i = 1; i <= n; i++) {
    Pow[i] = (Pow[i - 1] * base) % MOD;
}
for(int i = 1; i <= n; i++) {
    Hash[i] = (Hash[i - 1] * base + (s[i] - 'a' + 1)) % MOD;
    }
}

void solve() {
    cin >> s;
    __init__();
    for(int k = 1; k <= n; k++) {
        ll pre = getHash(1, k);
        ll suf = getHash(n - k + 1, n);
   //     cout << pre << ' ' << suf << endl;
        if(pre == suf) {
            a.push_back(k);
        }
    }
    sort(a.rbegin(), a.rend());
    if (a.empty()) {
        cout << "Just a legend\n";
    } else {
        int len = -1;
        for(auto k : a) {
            for(int i = 2; i <= n - k; i++) {
                if(getHash(i, i + k - 1) == getHash(1, k)) {
                    cout << s.substr(1, k) << endl; exit(0);
                }
            }
        }
        cout << "Just a legend\n";
      }
  }
  
  
int main(){
    faster()
    solve();
    return 0;
}

Cho một số n, tính tổng tất cả các chữ số từ 1 -> n

Input :

12

Ouput :

51

Giải thích : 1+2+3+4+5+6+7+8+9+1+2+3=51.

Bài này ta có thể sử dụng kỹ thuật Dynamic programming digit, nhưng mình sẽ dùng mảng cộng dồn và sàng trước các chữ số, vì giới hạn bài không quá lớn (1 ≤ n ≤ 2 * 10⁵).

• 🔹 Ta có công thức để tính mảng cộng dồn là :
• ✔️ dp[i] = dp[i - 1] + digit(i)

Quy trình thực hiện:

• 🟢 Bước 1: ta khởi tạo hàm digit() dùng để tách các chữ số từ 1 -> 2 * 10⁵
• 🟡 Bước 2: sử dụng mảng cộng dồn để sàng trước các giá trị, trong hàm __init__()
• 🔴 Lưu ý : nếu bạn không biết cách hoạt động của hàm __init__(), 100% sẽ bị time limit, vì không để đúng vị trí

📋 Copy

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define mem(a,b) memset(a, b, sizeof(a))
#define all(a) a.begin(), a.end()
#define sz(A) (int) A.size()
#define faster() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int N = 2e5 + 15;

vector<int>dp(N, 0);

int digit(int n) {
	int sum = 0;
	while(n) {
		sum = sum + (n % 10);
		n = n / 10; 
	}
	return sum; 
} 

void __init__() {
	dp[1] = 1;
	for(int i = 2; i <= N; i++) {
		dp[i] = dp[i - 1] + digit(i); 
	} 
} 

void solve() {
	int n; cin >> n;
	cout << dp[n] << endl; 
} 
int main(){
    faster();
    __init__();
    int t; cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}