题意
给定整数 \(n,k\)，现在你需要尝试构造一个长度为 \(k\) 的序列 \(a\)，使得 \(n=\sum\limits_{i=1}^n 2^{a_i}\)，\(a\) 中元素可以重复，要求 \(\max\{a_1,a_2,\cdots,a_k\}\) 尽可能小，且 \(a\) 的字典序尽可能大。如果存在这样的序列，输出 Yes 和序列 \(a\)，否则输出 No。
数据范围：\(1 \le n \le 10^{18}\)，\(1 \le k \le 10^5\)，保证最终答案中的数范围为 \([-10^{18},10^{18}]\)。
解法分析
模拟赛的时候打的这题。
当时做的时候看到这句“\(\max\{a_1,a_2,\cdots,a_k\}\) 尽可能小”，然后我就果断开始二分这个最大值了，但是事实上由于数据范围限制，我们其实直接枚举就可以，用不着二分（虽然二分快），脑抽了（捂脸）。
不过二分写法和枚举写法本质上其实是相同的，只是实现上有差异。设 \(\max\{a_1,a_2,\cdots,a_k\}=y\)，我们可以先二分（枚举）出这个 \(y\)，二分（枚举）条件就是 \(n\) 能否分解成不大于 \(k\) 个数的和，且这些数均不大于 \(y\)。得到这个 \(y\) 之后就可以算出字典序最大的 \(a\) 了。
- 二分（枚举）条件具体要怎么写？
实际上，根据同底数幂乘法，我们可以得到 \(2^i=2^{i-j}\cdot 2^j\)。所以，当 \(a_i > y\) 时，如果要分解 \(2^{a_i}\)，使得分解后的数均不大于 \(2^y\)，\(2^{a_i}\) 就要分解成 \(2^{a_i-y}\) 个 \(2^y\)。先将 \(n\) 分解为若干个不同 \(2^{a_i}\) 的和，再对对每个 \(a_i\) 进行一次这样的处理，然后算一下总共分解成了多少个数，比较下即可。
- 怎么得到字典序最大的 \(a\)？
我们会注意到一个情况：在算出了 \(y_{\min}\) 后，直接分解出的数的个数可能小于 \(k\)。比如 \(n=1,k=2\) 时，我们直接用上面的方法算出 \(y\) 后分解会分出 \(a=\{0\}\)，但显然长度没有达到 \(k\)。这时我们可以再次利用同底数幂乘法：\(2^i=2 \cdot 2^{i-1}\)。用这个式子对序列的最后一个数反复分解直到长度达到 \(k\) 为止即可，因为题目要求字典序最大。假设我们得到 \(k=4,a=\{1\}\)，\(a\) 就可以分解为 \(\{0,-1,-2,-2\}\)。容易发现这样分解之后字典序一定是最大的。
代码
这里就先只给二分写法了，普通枚举写法也差不多。
模拟赛的时候写的，巨丑，参考一下就好了。
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const ll K=1e5+7;
ll n,k,a[K];
bool check(ll mid) {
ll m=n,sum=0; vector <ll> v1;
while (m) v1.push_back(m%2),m/=2; //分解
for (ll i=0;i<v1.size();i++) if (v1[i]) {
if (i-mid>=31) return 0; //赛时脑抽写了个巨离谱的二分范围（在下面），就加了一个炸 long long 的特判，各位自己改一下吧
sum+=1<<max(0ll,i-mid); //左移可以代替 2 的幂次方
if (sum<0||sum>k) return 0; //请忽视 sum<0，也是脑抽加的
}
return 1;
}
int main() {
cin>>n>>k;
ll l=-1e18,r=1e18,mid,ans=2e18; //二分，各位如果要写二分的话请自行改一下范围（捂脸）
while (l<=r) {
mid=(l+r)/2;
if (check(mid)) r=mid-1,ans=mid;
else l=mid+1;
}
if (ans==2e18) cout<<"No"; //无解，即分解不了
else {
printf("Yes\n");
ll m=n,sum=0; vector <ll> v1,v2;
while (m) v1.push_back(m%2),m/=2;
for (ll i=v1.size()-1;i>=0;i--) if (v1[i]) {
for (ll j=0;j<(1<<max(0ll,i-ans));j++) v2.push_back(min(i,ans));
}
while (v2.size()<k) { //再次分解
ll r1=v2.back()-1;
v2.pop_back(),v2.push_back(r1),v2.push_back(r1);
}
for (auto i:v2) printf("%lld ",i);
}
return 0;
}