Thứ Hai, 9 tháng 11, 2020

Tìm tập hợp thỏa mãn tổng lowbit của các phần tử bằng sum cho trước, mỗi phần tử khác nhau từng đôi một và có giá trị không quá limit

Nguồn: $\href{https://codeforces.com/problemset/problem/437/B}{đây}$

 Tóm tắt: Tìm tập hợp thỏa mãn tổng lowbit của các phần tử bằng sum cho trước, mỗi phần tử khác nhau từng đôi một và có giá trị không quá limit

Lời giải: 

+ lowbit(x) chỉ bit 1 thấp nhất từ phải sang trái . Ví dụ: $lowbit(5)=lowbit(101)=2^1=2$

+ Ta cứ cho biến chạy trâu từ k trở về 1 , sau đó tham lam để tìm ra tập hợp

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define lowbit(x) ((x)&(-x))
  5. vector<ll> v;
  6. int main(){
  7. // freopen("input.inp","r",stdin);
  8. // freopen("output.out","w",stdout);
  9. ll n,k;
  10. cin>>n>>k;
  11. for(ll i=k;i>=1;i--){
  12. ll tmp = lowbit(i);
  13. if(n>=tmp){
  14. v.push_back(i);
  15. n-=tmp;
  16. }
  17. if(n==0) break;
  18. }
  19. if(n>0){cout<<-1;return 0;}
  20. cout<<v.size()<<'\n';
  21. for(auto p: v) cout<<p<<" ";
  22. return 0;
  23. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...