codeforces 960C Subsequence Counting

题目链接：http://codeforces.com/contest/960/problem/C

题意：对于任意包含n个元素的集合，他的子集有2^n-1个（不包括空集），然后现在告诉你某个集合的子集中，满足最大元素-最小元素差值<d的子集有x个，现在让你构造一个集合，使得满足上述条件。输出集合大小还有每个元素。集合元素个数大于10000输出-1。

分析：做这道题的时候一直在纠结什么情况输出-1，最后直接判断元素个数，如果大于10000，就输出-1.然后还有不知道自己的策略是不是最优策略，感觉不是最优策略但是AC了。具体思路是我们可以考虑对于任意一个有k个元素的集合，他有2^k-1个子集，如果这个集合的最大元素和最小元素差值小于d，那么所有子集都是满足的，因此可以对于他给定的x，拆分为元素个数为i个的小集合，小集合之间的最大元素和最小元素不满足情况，集合之内的一定满足就可以了。然后对于元素个数为i的小集合，我们只需要任意取i个相同元素就可以了。集合之间为了保证不满足，我们第一个集合从1开始，第二个就是1+d,以此类推就可以了。（我感觉这样不是最优，要想用最少的元素构造最多的满足条件的子集，比如现在要构造x=11，d=3的集合，如果用我的策略，需要构造1 1 1 4 4 7这6个元素来满足，但是如果我们用末尾添加策略（就是在已经构造好的集合最后添加一个元素，使得该元素与已有集合中的m个元素差值小于d，那么这次添加多出的满足条件的子集个数又增加了2^m个）的话，只需要1 2 3 4就可以满足了，所以我的策略应该不是最优，比赛刚打到一半有事出去了，没来的急码，大家可以尝试一下）

AC代码：（不太靠谱策略）

#include<bits/stdc++.h>

using namespace std;

long long a[50];
int b[50];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    long long x,d;
    a[0]=1;
    for(int i=1;i<=50;i++){
        a[i]=a[i-1]*2;
    }
    for(int i=0;i<=50;i++){
        a[i]--;
    }
    cin>>x>>d;
    long long n=0;
    memset(b,0,sizeof(b));
    for(int i=50;i>=1;i--){
        if(x>=a[i]){
            b[i]=x/a[i];
            x=x%a[i];
            n+=b[i]*i;
        }
    }
    if(n>10000) {
        cout<<-1<<endl;
        return 0;
    }
    cout<<n<<endl;
    long long ans=1;
    for(int i=1;i<=50;i++){
        for(int j=1;j<=b[i];j++){
            for(int k=0;k<i;k++){
                cout<<ans<<" ";
            }
            ans+=d;
        }
    }
    cout<<endl;
return 0;
}