标签：千夏 int ll long now sum

原题链接

题解

1.每一个1对答案的贡献为其前面0的个数
2.不难想到二进制，即每遇到 \(2^k\) 就考虑要不要放一个1
3.但是这样长度会超标，所以我们将较大的 \(2^k\) 表示成 \(2^{k_1}*2^{k_2}\)，其中 \(k_1+k_2==k\)，即在 0 的个数为 \(2^{k_1}\) 时后面放 \(2^{k_2}\) 个 1 ，而不是等达到了 \(2^k\) 个 0 后，再放一个 1
这样一来 \(2^{k_1}+2^{k_2}<2^k\)

code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll inf=1e5;
vector<int> q,ans;
int main()
{
    ll sum;
    cin>>sum;
    while(sum)
    {
        q.push_back(sum%2);
        sum/=2;
    }


    ll len=q.size();
    for(int i=0;i<len/2;i++)
    {
        for(int j=1;j<=(1LL<<(max(0LL,(i-1LL))));j++) ans.push_back(0);
        if(q[i]) ans.push_back(1);
    }

    ll now=0;
    for(int i=len-1;i>=len/2;i--) now=now*2+q[i];

    for(int i=1;i<=(1LL<<max(0LL,(len/2-1LL)));i++) ans.push_back(0);
    for(int i=1;i<=now;i++) ans.push_back(1);
    cout<<ans.size()<<endl;
    for(auto it:ans) cout<<it;
    return 0;
}

标签：千夏,int,ll,long,now,sum
From： https://www.cnblogs.com/pure4knowledge/p/18254252