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:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define lowbit(x) ((x)&(-x))
- vector<ll> v;
- int main(){
- // freopen("input.inp","r",stdin);
- // freopen("output.out","w",stdout);
- ll n,k;
- cin>>n>>k;
- for(ll i=k;i>=1;i--){
- ll tmp = lowbit(i);
- if(n>=tmp){
- v.push_back(i);
- n-=tmp;
- }
- if(n==0) break;
- }
- if(n>0){cout<<-1;return 0;}
- cout<<v.size()<<'\n';
- for(auto p: v) cout<<p<<" ";
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét