SPOJ Solution

Cho hai chuỗi **needle** và **haystack**, tìm tất cả vị trí xuất hiện của **needle** trong **haystack**.

Ví dụ:

Input:

2
na
banananobano
                            

Output:

2
4

Giải thích: "na" xuất hiện tại vị trí **2** và **4**.

🔹 Bài toán sử dụng **Hashing (Rolling Hash)** để tìm kiếm chuỗi con nhanh chóng.

Ý tưởng chính:

• **Tiền xử lý**: Tính giá trị hash của chuỗi **needle** và prefix hash của **haystack**.
• Sử dụng công thức **getHash(l, r)** để lấy hash của từng đoạn con trong **haystack**.
• So sánh hash để tìm tất cả vị trí khớp với **needle**.

Quy trình thực hiện:

• 🟢 Bước 1: Tiền xử lý mảng **Pow** (lũy thừa của base) và **Hash** (prefix hash của **haystack**).
• 🟡 Bước 2: Duyệt từng vị trí trong **haystack**, so sánh hash với **needle**.
• 🔴 Bước 3: Nếu khớp, in ra vị trí xuất hiện.

Độ phức tạp: O(n + m), nhanh hơn nhiều so với phương pháp brute-force.

📋 Copy

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define ed cout << "\n"
#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 ll MOD = 1e9 + 9;
const int base = 31;
vector<ll>Hash, Pow;
string a, b;
ll n, m, k, HashA, ok;
 
void __init__() {
    a = ' ' + a;
    b = ' ' + b;
    n = a.length() - 1, m = b.length() - 1;
    Hash.assign(m + 1, 0);
    Pow.assign(m + 1, 0);
    Pow[0] = 1; HashA = 0; ok = 0;
    for(int i = 1; i <= m; i++) {
        Pow[i] = (Pow[i - 1] * base) % MOD;
        Hash[i] = (Hash[i - 1] * base + (b[i] - 'a' + 1)) % MOD;
    }
    for(int i = 1; i <= n; i++) {
        HashA = (HashA * base + (a[i] - 'a' + 1)) % MOD;
    }
}
 
ll getHash(int l, int r) {
    return (Hash[r] - Hash[l - 1] * Pow[r - l + 1] % MOD + MOD) % MOD;
}
 
void solve() {
    while(cin >> n) {
        cin >> a >> b;
        __init__();
        for(int i = 1; i <= m - n + 1; i++) {
            if(getHash(i, i + n - 1) == HashA) {
                cout << i - 1 << endl;
                ok = 1;
            }
        }
        if(!ok) ed;
    }
}
 
int main(){
    faster();
    solve();
    return 0;
}  

Cho một cái túi có sức chứa **S** và **N** món đồ, mỗi món có kích thước và giá trị.

• Nhiệm vụ: Chọn một tập hợp đồ sao cho tổng giá trị lớn nhất mà không vượt quá sức chứa.

Input:

4 5
1 8
2 4
3 0
2 5
2 3

Output:

13

Giải thích: Chọn các món có giá trị 8, 5, tổng giá trị lớn nhất là **13**.

Bài này sử dụng quy hoạch động (Dynamic Programming) để giải bài toán Knapsack.

• Ta tạo một mảng **dp[i][j]** đại diện cho giá trị lớn nhất có thể đạt được với **i** món đồ và sức chứa **j**.
• Nếu không chọn món thứ **i**, giá trị vẫn là **dp[i-1][j]**.
• Nếu chọn món thứ **i** (nếu vừa túi), ta cập nhật giá trị lớn hơn giữa **dp[i][j]** và **dp[i-1][j - w[i]] + v[i]**.

Quy trình thực hiện:

• 🟢Bước 1: Khởi tạo mảng **dp** với giá trị ban đầu bằng 0.
• 🟡Bước 2: Duyệt qua từng món đồ, cập nhật giá trị lớn nhất có thể đạt được.
• 🟠Bước 3: In ra kết quả là giá trị lớn nhất tìm được.

📋 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 = 2e6 + 15;
const int MOD = 1e9 + 7;
const int INF = 1e5 + 1;
const int mxn = 1000 + 15;
 
vector<vector<int>>dp;
vector<int>w, v;
int n, sz, ans = -1;
void solve() {
	cin >> sz >> n;
	dp.assign(n + 1, vector(sz + 1, 0));
	w.assign(n + 1, 0);
	v.assign(n + 1, 0);
	for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= sz; j++) { 
			dp[i][j] = dp[i - 1][j];
			if(w[i] > j) continue;
			dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);             
			ans = max(ans, dp[i][j]);                 
		}
	}
	cout << ans << endl;
}
int main() {
    faster();
    //freopen("input.INP", "r", stdin);
   // freopen("output.OUT", "w", stdout);
    int t; t = 1; 
    //cin >> t;
    while(t--){
    	clock_t z = clock();
    	solve();
    	debug("Total Time: %.3f\n", (double)(clock() - z) / CLOCKS_PER_SEC);
    	if(t != 0) ed;
	}
    return 0;
}

Cho hai số nguyên không âm **a** và **b**, tính tổng tất cả các chữ số xuất hiện trong khoảng **[a, b]**.

Input :

a = 28, b = 31

Output :

28

Giải thích : 2+8 + 2+9 + 3+0 + 3+1 = 28

Bài này sử dụng kỹ thuật **quy hoạch động số học (Digit DP)** để tính tổng chữ số của tất cả các số trong khoảng **[a, b]** một cách hiệu quả.

• 🔹 Ý tưởng chính:
• ✔️ **Tính tổng chữ số của tất cả các số từ 1 đến x** bằng phương pháp đệ quy với nhớ trạng thái (Memoization).
• ✔️ Sau đó, tổng chữ số của **[a, b]** chính là hiệu của tổng chữ số từ **1 đến b** trừ đi tổng chữ số từ **1 đến a-1**.

Quy trình thực hiện:

• 🟢 Bước 1: Chuyển số **x** thành mảng chữ số.
• 🟡 Bước 2: Dùng **quy hoạch động** để duyệt từng chữ số từ trái sang phải, giữ trạng thái tổng chữ số và kiểm soát giới hạn.
• 🟠 Bước 3: Kết quả cuối cùng là **getSum(b) - getSum(a-1)**.

📋 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 = 1e5 + 15;
 
int64_t dp[19][180][2];
ll q, l, r;
 
int64_t f(vector<int>& a, int pos, int sum, int fl) {
    if(pos >= a.size()) return sum;
    int64_t &nemo = dp[pos][sum][fl];
    if(nemo != -1) return nemo;
    int limit = fl ? a[pos] : 9;
    nemo = 0;
    for(int i = 0; i <= limit; i++) {
        nemo = nemo + f(a, pos + 1, sum + i, fl && (i == limit));
    }
    return nemo;
}
 
vector<int> getDigits(ll x) {
    vector<int>nums;
    while(x) {
        nums.push_back(x % 10);
        x = x / 10;
    }
    reverse(all(nums));
    return nums;
}
 
int64_t getSum(ll x) {
    if(x <= 0) return 0;
    mem(dp, -1);
    vector<int>digits = getDigits(x);
    return f(digits, 0, 0, 1);
}
 
int main(){
    faster()
    cin >> q;
    while(q--) {
        cin >> l >> r;
        cout << getSum(r) - getSum(l - 1) << endl;
    }
    return 0;
}