CSES Solution

Bạn có n loại tiền xu, mỗi loại có một giá trị nguyên dương khác nhau. Nhiệm vụ của bạn là tìm cách tạo ra tổng tiền x bằng cách sử dụng số lượng ít nhất các đồng xu có sẵn.

Ràng buộc:

• \(1 \leq n \leq 100\)
• \(1 \leq x \leq 10^6\)
• \(1 \leq c_i \leq 10^6\)

Input:

• Dòng đầu tiên chứa hai số nguyên n (số lượng loại tiền) và x (tổng tiền cần tạo).
• Dòng thứ hai chứa n số nguyên c₁, c₂, ..., cₙ (giá trị của từng loại tiền xu).

Output:

• Một số nguyên duy nhất: số lượng ít nhất các đồng xu cần dùng để tạo tổng x.
• Nếu không thể tạo ra tổng x, in -1.

Ví dụ:

Input:

3 11
1 5 7
        

Output:

3
        

Giải thích:

• Ta có thể tạo ra 11 bằng cách dùng 5 + 5 + 1, tổng cộng 3 đồng xu, đây là cách tối ưu nhất.

🔹 Bài toán này có thể được giải quyết bằng phương pháp quy hoạch động (Dynamic Programming - DP).

Ý tưởng:

• 🟢 Bước 1: Khởi tạo mảng dp với dp[i] là số đồng xu tối thiểu để tạo ra tổng i. Ban đầu, gán tất cả các giá trị là 1e9 (vô cực) trừ dp[0] = 0.
• 🟡 Bước 2: Duyệt qua từng loại đồng xu và cập nhật dp[j] với dp[j] = min(dp[j], dp[j - coin] + 1) nếu có thể tạo thành tổng j.
• 🔴 Bước 3: Nếu dp[x] vẫn là vô cực, in -1. Ngược lại, in dp[x] là số đồng xu ít nhất cần dùng.

📋 Copy

#include <bits/stdc++.h>
using namespace std;
 
 
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define pb push_back
#define ed cout << "\n"
#define no cout << "NO\n"
#define ye cout << "YES\n"
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOD(i, r, l) for (int i = r; i >= l; i--)
#define FOB(i, l, r) for (int i = l; i < r; i++)
#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)
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
const int N = 2e6 + 15;
const int MOD = 1e9 + 7;
const int INF = 1e5 + 1;
const int mxn = 1000 + 15;
 
int nxt() { int x; cin >> x; return x; }
void add(int &a, int b) {
//	a = (a + b) % MOD;
    a = a + b;
    if (a >= MOD) a = a - MOD;
    if (a < 0) a = a + MOD;
}
void mul(int &a, int b) {
    ll res = ((ll)a * b) % MOD;
    a = res;
}
 
void Fami(int n, vector<int>& a) {
	
}
 
void solve() {
	int n = nxt(), sz = nxt();
	vector<int>dp(sz + 1, 1e9);
	vector<int>a(n);
	for(auto &x : a) x = nxt();
	dp[0] = 0; 
	for(int i = 0; i < n; i++) {
		for(int j = a[i]; j <= sz; j++) {
			dp[j] = min(dp[j], dp[j - a[i]] + 1);
		}
	}
	cout << ((dp[sz] == 1e9) ? -1 : dp[sz]) << 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 một công ty với n nhân viên, mỗi nhân viên (trừ giám đốc) có một cấp trên trực tiếp.

• Nhiệm vụ: Tính số lượng cấp dưới của từng nhân viên.
• Nhân viên số 1 là giám đốc chung của công ty.

Input:

• Dòng đầu chứa số nguyên n - số nhân viên.
• Dòng thứ hai chứa n-1 số nguyên, trong đó số thứ i là cấp trên trực tiếp của nhân viên i+1.

Output:

• In ra n số nguyên, số thứ i là số cấp dưới của nhân viên i.

Ví dụ:

Input:

5
1 1 2 3

Output:

4 1 1 0 0

Giải thích:

• Nhân viên 1 có 4 cấp dưới (gồm tất cả những nhân viên còn lại).
• Nhân viên 2 có 1 cấp dưới (nhân viên 3).
• Nhân viên 3 có 1 cấp dưới (nhân viên 4).
• Nhân viên 4 và 5 không có cấp dưới.

🔹 Bài này ta sử dụng DFS để tính số lượng cấp dưới của từng nhân viên.

Quy trình thực hiện:

• 🟢 Bước 1: Tạo danh sách kề lưu quan hệ sếp - nhân viên.
• 🟡 Bước 2: Sử dụng DFS để duyệt từ giám đốc (nhân viên 1) xuống.
• 🔵 Bước 3: Với mỗi nhân viên, tính tổng số lượng nhân viên cấp dưới của họ.

Độ phức tạp: O(n), vì mỗi nhân viên chỉ được duyệt một lần.

📋 Copy

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

 
#define faster() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define ed cout << "\n"
const int N = 2e5 + 15;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 1;
const int mxn = 2000 + 15;
using ll = long long;
 
int dp[N];
vector<int>adj[N];
bool vis[N];
int n, m;
 
void dfs(int u) {
	dp[u] = dp[u] + 1;
	for(auto v : adj[u]) {
		dfs(v);
		dp[u] = dp[u] + dp[v];
	}
}
 
void solve() {
	cin >> n;
	for(int i = 2; i <= n; i++) {
		int x; cin >> x;
		adj[x].push_back(i);
	}
	dfs(1);
	for(int i = 1; i <= n; i++) cout << dp[i] - 1 << ' ';
}
 
 
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 một mảng gồm n số nguyên và q truy vấn.

• Mỗi truy vấn yêu cầu tính tổng các phần tử trong khoảng [a, b].

Input :

• Dòng đầu gồm hai số nguyên n và q (số phần tử và số truy vấn).
• Dòng thứ hai chứa n số nguyên là các phần tử của mảng.
• Mỗi trong q dòng tiếp theo chứa hai số a, b (chỉ số bắt đầu và kết thúc của truy vấn).

Output : Với mỗi truy vấn, in ra tổng các phần tử trong khoảng [a, b].

Ví dụ:

Input:

8 4
3 2 4 5 1 1 5 3
2 4
5 6
1 8
3 3
        

Output:

11
2
24
4
        

Bài này ta sử dụng cấu trúc dữ liệu Segment Tree để xử lý truy vấn nhanh chóng.

• 🔹 Segment Tree cho phép tính tổng đoạn trong O(log n) thay vì O(n) khi duyệt tuyến tính.
• 🔹 Ta xây dựng cây trong O(n) và xử lý mỗi truy vấn trong O(log n).

Quy trình thực hiện:

• 🟢 Bước 1: Xây dựng cây bằng phương pháp chia đôi mảng (Build Segment Tree).
• 🟡 Bước 2: Khi có truy vấn tìm tổng đoạn [l, r], ta duyệt nhanh trên cây để lấy kết quả.
• 🟠 Bước 3: Nếu cần cập nhật giá trị tại vị trí pos, ta cập nhật trên cây để không cần xây lại toàn bộ.

Chi tiết thuật toán:

• ✔️ Xây dựng cây: Mỗi nút lưu tổng của một đoạn con.
• ✔️ Truy vấn tổng đoạn: Nếu đoạn con nằm hoàn toàn trong [l, r], trả về ngay.
• ✔️ Cập nhật phần tử: Cập nhật giá trị tại vị trí pos và cập nhật lại cây.

📋 Copy

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
#define fi first
#define se second
#define pb push_back
#define ed cout << "\n"
#define no cout << "NO\n"
#define ye cout << "YES\n"
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FOD(i,r,l) for (int i=r;i>=l;i--)
#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;
 
// #ifdef ONLINE_JUDGE
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
// #endif
 
ll t[4 * N], a[N];
int n, q;
void build(int v, int tl, int tr) {
    if(tl == tr) {
        t[v] = a[tl];
    } else {
        int mid = (tl + tr) >> 1;
        build(v << 1, tl, mid);
        build(v << 1 | 1, mid + 1, tr);
        t[v] = t[v << 1] + t[v << 1 | 1];
    }
}
 
void update(int v, int tl, int tr, int pos, int val) {
    if(tl == tr) {
        t[v] = val;
    } else {
        int mid = (tl + tr) >> 1;
        if(pos <= mid) {
            update(v << 1, tl, mid, pos, val);
        } else {
            update(v << 1 | 1, mid + 1, tr, pos, val);
        }
        t[v] = t[v << 1] + t[v << 1 | 1];
    }
}
 
ll query(int v, int tl, int tr, int l, int r) {
    if(l > tr || r < tl) return 0;
    if(l <= tl && tr <= r) {
        return t[v];
    } else {
        int mid = (tl + tr) >> 1;
        ll left = query(v << 1, tl, mid, l, r);
        ll right = query(v << 1 | 1, mid + 1, tr, l, r);
        return left + right;
    }
}
 
void solve() {
    cin >> n >> q;
	for(int i = 0; i < n; i++) cin >> a[i];
	build(1, 0, n - 1);
    while(q--){
		int x, y; cin >> x >> y;
		x--; y--;
		cout << query(1, 0, n - 1, x, y) << endl;
	}
}
 
int main(){
    faster()
    solve();
    return 0;
}