Open utterances-bot opened 1 year ago
Dùng phương pháp sinh để tính tổng các tập con cũng AC nha
Dùng phương pháp sinh để tính tổng các tập con cũng AC nha
anh ơi anh có thể nói rõ về phương pháp này được ko ạ? chứ em hỏi bác gg mà ko ra :)))
Dùng phương pháp sinh để tính tổng các tập con cũng AC nha
anh ơi anh có thể nói rõ về phương pháp này được ko ạ? chứ em hỏi bác gg mà ko ra :)))
Bạn dùng phương pháp sinh để tạo ra một tổ hợp các số dạng 0 và 1, ví dụ với n bằng 3 thì ta có các tổ hợp: 000, 001, 010, 011, 100, 101, 110, 111 với ý nghĩa: 0: không chọn số ở vị trí index đó để tính tổng. 1: chọn số ở vị trí đó để tính tổng. Dựa vào các dãy đó để tính tổng các quả cân. Sau khi tính và lưu trữ lại tất cả các trường hợp tổng của n quả cân có thể xảy ra vào một mảng (ví dụ mảng F), ta duyệt qua m khối lượng của mặt hàng, nếu mặt hàng thứ i tồn tại trong mảng F, tức là có thể cân được, ngược lại là không cân được.
không hiểu code sai ở đâu :V
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, f[1000001], m, d;
vector <ll> a;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("a.inp", "r", stdin);
// freopen("a.out", "w", stdout);
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> f[i];
}
for(int i = 1; i <= m; i ++){
cin >> d;
ll s = n + 1;
while(d != 0){
s = upper_bound(f + 1, f + s, d) - f - 1;
d -= f[s];
if(s == 0 && d != 0)break;
}
if(d != 0) cout << 0;
else cout << 1;
}
}
Chi tiết bài tập - Luyện Code Online
https://oj.luyencode.net/problem/BLSCALES